学步园

还是欧拉函数，写的有点特殊。。。

在去A一次， 用正常人得做法。。。。。

//正常人不要学习我的方法。。。。。
//看看取乐的了。。。。
#include <stdio.h>
#include <math.h>
#include <string.h>
__int64 prime[10000], visit[10000], len;
//筛素数
__int64 Prime()
{
	__int64 i, j;
	len = 0;
	memset(visit, 0, sizeof(visit));
	for (i = 2; i <= 10000; i++)
	{
		if (visit[i] == 0)
		{
			for (j = 2 * i; j <= 10000; j += i)
				visit[j] = 1;
			prime[len++] = i;
		}
	}
}
int main()
{
	__int64 i, n, cnt, temp, p_factor[10000], phi;
	Prime();
	while (scanf("%I64d", &n) && n)
	{
		temp = n;
		//剔除质因素并保留在数组p_factor中
		for (i = cnt = 0; i < len; i++)
		{
			if (temp == 0 || temp == 1) break;
			if (temp % prime[i] == 0)
			{
				p_factor[cnt++] = prime[i];
				while (temp && temp % prime[i] == 0) { temp /= prime[i]; }
			}
		}
		//没有被10000以内的素数整除一定是素数
		if (cnt == 0)
			printf("0\n");
		else
		{
			//素因子可能大于10000
			//就这儿纠结了好久
			if (temp != 1)
				p_factor[cnt++] = temp;
			phi = n;
			for (i = 0; i < cnt; i++)
			{
				phi = phi / p_factor[i] * (p_factor[i] - 1);
				//printf("%d ", p_factor[i]);
			}
			//printf("\nPHI = %d cnt = %d\t", temp, cnt);
			printf("%I64d\n", n - phi - 1);
		}
	}
	return 0;
}

A掉了。。。

#include <stdio.h>
__int64 Euler(int n)
{
	__int64 i, ans = n;
	for (i = 2; i < 10000; i++)
		if (n % i == 0)
		{
			ans = ans / i * (i-1);
			while (n % i == 0) { n /= i; }
			if (n == 1) break;
		}
	if (n > 10000)
		ans = ans / n * (n-1);
	return ans;
}
int main()
{
	__int64 n;
	while (scanf("%I64d", &n))
	{
		if (n == 0) break;
		printf("%I64d\n", n - Euler(n) - 1);
	}
	return 0;
}