首页 > 代码库 > HDU 1286 欧拉函数。

HDU 1286 欧拉函数。

2024-10-21 18:30:02   202人阅读

<marquee width="600">

 

【科普】什么是BestCoder？如何参加？

</marquee>

找新朋友

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8077    Accepted Submission(s): 4250


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

2
25608
24027

 


 

Sample Output

7680
16016

 


 

Author

SmallBeer(CML)

 


 

Source

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

 

 

 

 

欧拉乃真神人不知道怎么证明的 。

其实题意就是这个：在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler‘s totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。 从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。

找出和m互质的。

上代码吧。

#include<string.h>  
#include <stdio.h>
int g[32770];  
int ouler(int x)  
{  
    int i,k=1;  
    int m=x;  
    for(i=2;i<=m;i++)  
    {  
        if(m%i==0)  
        {  
            k=k*(i-1);  
            while(m%i==0)  
            {  
				m=m/i;  
                k*=i;  
            }  
            k/=i;  
        }  
    }  
    return k;    //以上是查资料写出的，至于为什么是这样的因为证明实在看不懂，我不知道。
}  
int main()  
{  
    int ncase,m;  
    scanf("%d",&ncase);  
    while(ncase--)  
	{  
        scanf("%d",&m);  
        printf("%d\n",ouler(m));  
    }  
	return 0;  
}


 

 

HDU 1286 欧拉函数。


联系
我们