2978578_ac_312ms_11916k.cc

北大大牛代码 1240道题的原代码 超级权威

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

int fai[1000001];
__int64 f[1000001];

void Fai()
{
	int sushu[200];
	int i, j, c;
	int comp[1000];

	fai[1] = 1;
	memset(comp,0,sizeof(comp));
	sushu[0] = 2;
	c = 0;
	for(i = 2; i < 1000; i++)
	{
		if(!comp[i])
		{
			for(j = i * 2; j < 1000; j += i)
			{
				comp[j] = 1;
			}
		}
	}
	for(i = 2; i < 1000; i++)
	{
		if(!comp[i])
		{
			sushu[c ++] = i;
		}
	} 
	for(j = 2; j < 1000001; j ++)
	{
		for(i = 0; i < c ;i ++)
		{
			int k = j/sushu[i];
			if(j%sushu[i] == 0)
			{
				if(k%sushu[i] == 0)
					fai[j] = fai[k]*sushu[i];
				else
					fai[j] = fai[k]*(sushu[i] - 1);
				break;
			}
		}
		if(i == c)
			fai[j] = j - 1;
	}

}

void init()
{
	int i;

	Fai();
	f[2] = 1;
	for(i = 3; i < 1000001; i++)
	{
		f[i] = fai[i];
		f[i] += f[i-1];
	}
}

int main()
{
	int n;

	init();
	while(scanf("%d",&n),n)
		printf("%I64d\n",f[n]);
	return 0;
}