找新朋友

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 7651 Accepted Submission(s): 4033

Problem Description

新年快到了，“猪头帮协会”准备搞一个聚会，已经知道现有会员N人，把会员从1到N编号，其中会长的号码是N号，凡是和会长是老朋友的，那么该会员的号码肯定和N有大于1的公约数，否则都是新朋友，现在会长想知道究竟有几个新朋友？请你编程序帮会长计算出来。

Input

第一行是测试数据的组数CN（Case number，1<CN<10000），接着有CN行正整数N（1<n<32768），表示会员人数。

Output

对于每一个N，输出一行新朋友的人数，这样共有CN行输出。

Sample Input

Sample Output

7680

16016

Author

SmallBeer(CML)

Source

杭电ACM集训队训练赛（VII）

Recommend

lcy | We have carefully selected several similar problems for you: 1215 1406 1164 1787 1211

求约数直接筛的裸算法过了。。

查题解发现有欧拉函数这个东西

在数论中，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数、欧拉商数等。

φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn) 其中p1,
p2……pn为x的所有质因数

因此先打个素数表求他是那些素数然后直接用欧拉公式即可；

1.用约数筛

#include<stdio.h>

#include<math.h>

#include<string.h>

int yueshu[200];

int yuenum;

int ok[40000];

int ans=0;

int main()

{

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

	int CN,i,N,mem,j,t,k;

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

	{

		for(i=1;i<=CN;i++)

		{

			memset(yueshu,0,sizeof(yueshu));

			memset(ok,0,sizeof(ok));

			yuenum=1;

			ans=0;

			scanf("%d",&mem);

			t=sqrt(mem);

			for(j=1;j<=t;j++)

			if(mem%j==0)

			{

				yueshu[yuenum++]=j;

				yueshu[yuenum++]=mem/j;

			}

			yuenum--;

			for(j=2;j<=yuenum;j++)

			{

				for(k=1;k*yueshu[j]<=mem;k++)

				ok[k*yueshu[j]]=1;

			}

			for(j=1;j<=mem;j++)

			if(ok[j]==0) ans++;

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

		}

	}

	return 0;

}

2.O（n）级别素数筛选+欧拉

#include<stdio.h>

int YNprime[40001];

int prime[40000];

int totprime=1;

int get_prime(int maxn)

{

	int i,j;

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

	 {

	   	if(YNprime[i]==0) prime[totprime++]=i;

	   	for(j=1;i*prime[j]<=maxn&&j<totprime;j++)

	   	{

	   		YNprime[i*prime[j]]=1;

	   		if(i%prime[j]==0) break;

		}

	}

}

int main()

{

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

	get_prime(40000);

	int CN,N,i,j,ans;

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

	{

		for(i=1;i<=CN;i++)

		{

			scanf("%d",&N);

			ans=N;

			if(N==1) { printf("0\n");continue;}

			for(j=1;prime[j]<=N&&j<totprime;j++)

			{

			if(N%prime[j]==0)

			ans=(ans/prime[j])*(prime[j]-1);

			}

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

		}

	}

	return 0;

}

但有个更优美的代码：

用最小的素因子筛掉每个数

int prime[N],phi[N],cnt;// prime:记录质数，phi记录欧拉函数

int Min_factor[N];// i的最小素因子

bool vis[N];

void Init()

{

    cnt=0;

    phi[1]=1;

    int x;

    for(int i=2;i<N;i++)

    {

        if(!vis[i])

        {

            prime[++cnt]=i;

            phi[i]=i-1;

            Min_factor[i]=i;

        }

        for(int k=1;k<=cnt&&prime[k]*i<N;k++)

        {

            x=prime[k]*i;

            vis[x]=true;

            Min_factor[x]=prime[k];

            if(i%prime[k]==0)

            {

                phi[x]=phi[i]*prime[k];

                break;

            }

            else phi[x]=phi[i]*(prime[k]-1);

        }

    }

}

巴特西

【欧拉函数】【HDU1286】找新朋友

找新朋友

最新文章

热门文章

巴特西

【欧拉函数】【HDU1286】 找新朋友

找新朋友

最新文章

热门文章

【欧拉函数】【HDU1286】找新朋友