3090120_ac_15ms_164k.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 90 行

#include <math.h>
#include <stdio.h>
#include <string.h>

int num[100], c[100], n, nn, no, used[100];
__int64 ans;

int fai(int mm)
{
	int i, nu;
	
	nu = mm;
	for(i = 0; i < no; i++)
	{
		if(used[i])
		{
			nu -= nu/c[i];
		}
	}
	return nu;
}

void dfs(int l,int p)
{
	int i, t;
	__int64 tt, pp;

	if(l==no)
	{
		tt = fai(p);
		pp = nn/p;
		ans += tt*pp;
		return ;
	}
	t = 1;
	for(i = 0; i <= num[l]; i++)
	{
		used[l] = i;
		dfs(l+1,p*t);
		t *= c[l];
	}
}

int main()
{
	int i, q;

	while(scanf("%d",&n)==1)
	{
		nn = n;
		memset(num,0,sizeof(num));
		no = 0;
		if (n%2==0)
		{
			c[no] = 2;
			while (n%2==0)
            {
				n /= 2;
				num[no]++;
			}
			no++;
		}
		q = (int)sqrt(n)+1;
		for (i = 3; i < q&&n!=1; i+=2)
		{
			if (n%i==0)
			{
				c[no] = i;
				while (n%i==0)
				{
					n /= i;
					num[no]++;
				}
				q = (int)sqrt(n)+1;
                no++;
			}
		}
		if (n!=1)
		{
			c[no] = n;
			num[no]++;
			no++;
		}
		ans = 0;
		dfs(0,1);
		printf("%I64d\n",ans);
	}
	return 0;
}