hdu3501Calculation 2——欧拉函数模板

题目：

Problem Description

Given a positive integer N, your task is to calculate the sum of the positive integers less than N which are not coprime to N. A is said to be coprime to B if A, B share no common positive divisors except 1.

Input

For each test case, there is a line containing a positive integer N(1 ≤ N ≤ 1000000000). A line containing a single 0 follows the last test case.

Output

For each test case, you should print the sum module 1000000007 in a line.

Sample Input

3 4 0

Sample Output

0 2

欧拉函数模板：

先求出φn；

由gcd(n,i)=1得gcd(n,n-i)=1，则与n互素的数之和=φ(n)*n/2；

则ans=小于n的数之和-φ(n)*n/2（注意这里不能为“-φ(n)/2*n”或“-n/2*φ(n)”，先/2可能变成0）。

以下为代码：

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

long long n,res,ans;

int main()

{

	while(1)

	{

		scanf("%lld",&n);

		if(!n)return 0;

		res=n;

		int nn=n;

		for(int i=2;i*i<=nn;i++)

		{

			if(nn%i==0)

			{

				res-=res/i;//减去其中素因子i的倍数的个数 

//				res=res/i*(i-1);

				while(nn%i==0)nn/=i;//提走素因子i 

			}

		}

		if(nn>1)res-=res/nn;//不能是res--!

//		if(nn>1)res=res/n*(n-1);

		ans=(n*(n-1)/2-n*res/2)%1000000007;

		printf("%lld\n",ans);

	}

	return 0;

}

巴特西

hdu3501Calculation 2——欧拉函数模板

最新文章

热门文章