gcd again(欧拉函数).cpp

杭电acm解题报告2001---2099.

//N的范围比较大,10^8
//如果求10^8范围内的素数肯定MLE
//小于n且与n互素的数的个数叫做n的欧拉φ函数。假设n的素因子标准分解表达式为
//N=P1^t1*P2^t2…Pq^tq , 则有：φ(n)=n(1-1/P1) (1-1/P2)…(1-1/Pq)
//N如果不能被10^4以内的素数分解的话,说明他的素因子必定都大于10^4
//但10^4*10^4 = 10^8, 所以它不会有2个或者2个以上的大于10^4的素因子
//则当10^4以内的素数对它分解完以后,剩下的值就是它的一个素因子,并且唯一
#include <cstdio>
#include <string>
#include <cmath>
#define Max 10100
int prime[2000],size;
bool num[Max+100];
int n;

void cal_prime()
{
	int i,j;
	size = 0;
	for (i=2;i<=sqrt(1.0*Max);i++) {
		if (!num[i]) {
			for (j=i*i;j<=Max;j+=i) {
				num[j] = true;
			}
		}
	}
	for (i=2;i<=Max;i++) {
		if (!num[i]) {
			prime[size++] = i;
		}
	}
}

int euler()
{
	int i = 0, t = n;
	double ans = n;
	bool flag;
	while (i<size) {
		if (t <= 1) {
			break;
		}
		flag = false;
		while (t%prime[i]==0) {
			t /= prime[i];
			flag = true;
		}
		if (flag) {
			ans *= 1- 1.0/prime[i];
		}
		i++;
	}
	if (t > 1) {
		ans *= 1- 1.0/t;
	}
	return (int)ans;
}

int main()
{
	int i,j;
	
	cal_prime();
	while (scanf("%d",&n),n) {
		printf("%d\n", n - euler() -1);
	}
}