51Nod-1136 欧拉函数

51Nod： http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1136

基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题

对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。例如：φ(8) = 4（Phi(8) = 4），因为1,3,5,7均和8互质。

Input

输入一个数N。(2 <= N <= 10^9)

Output

输出Phi(n)。

Input示例

Output示例

题解：

（1），对N进行因子分解，得到若干个素因子，那么在 [1, n] 之间，凡是这些素因子的倍数都是与N不互素的

（2），使用容斥原理，对于素因子 P1, p2, ... pK, 比如P1就存在着 [p1, 2*p1, 3*p1, ... num1*p1], (num1*p1 <= N), 可以得到：num1 = n/p1;

（3），另外多个素因子之间可能重复计算了公倍数，利用 Num(p1) + Num(p2) + Num(p2) - Num(p1*p2) - Num(p2*p3) - Num(p3*p1) + Num(p1*p2*p3) 计算出实际的个数。

（4），最后，[1, N] 之间有N 个数字，所以， N - 素因子及其倍数的个数，得到答案。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

using namespace std; 

const int maxn = 2000000;

const int maxm = 100000; 

bool prime[maxn];

int  cnt, p[maxm], fac[maxm], output[maxm]; 

void IsPrime(){

	memset(prime, false, sizeof(prime));

	cnt = 0;

	for(int i=2; i<maxn; ++i){

		if(!prime[i]){

			p[cnt++] = i;

			for(int j=i+i; j<maxn; j+=i){

				prime[j] = true;

			}

		}

	}

}

int solve(int n){

	int k, num = 0, t = 0, tmp = n;

	for(int i=0; p[i]*p[i]<=n; ++i){

		if(n%p[i] == 0){

			fac[num++] = p[i];

			while(n%p[i]==0){ n=n/p[i]; }

		}

	}

	if(n > 1){

		fac[num++] = n;

	}

	output[t++] = -1;

	for(int i=0; i<num; ++i){

		k = t;

		for(int j=0; j<k; ++j){

			output[t++] = output[j]*fac[i]*(-1);

		}

	}

	int sum = 0;

	for(int i=1; i<t; ++i){

		sum = sum + tmp/output[i];

	}

	return sum;

}

int main(){

	//freopen("in.txt", "r", stdin); 

	IsPrime();

	int ans, n;

	while(scanf("%d", &n) != EOF){

		ans = solve(n);

		printf("%d\n",  (n - ans) );

	}

	return 0;

}

Reference： http://www.cnblogs.com/jiangjing/archive/2013/06/03/3115470.html

秒客网

51Nod-1136 欧拉函数

相关文章