首页 > ACM题库 > HDU-杭电 > HDU 1286 找新朋友-数论-[解题报告] C++
2013
12-04

HDU 1286 找新朋友-数论-[解题报告] C++

找新朋友

问题描述 :

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

输入:

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

输出:

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

样例输入:

2
25608
24027

样例输出:

7680
16016

http://acm.hdu.edu.cn/showproblem.php?pid=1286

学到了筛法求欧拉函数。即欧拉函数φ(n)表示≤n且与n互素的正整数的数目(其实等于仅对1而言,φ(1)=1,1被认为与任何数互素)。
编程求一个数的φ(n)显然很简单,用gcd()就可以了,但如果求一个很大范围(N)内所有数的欧拉函数值,gcd()就难以胜任了。
在网上找了一下,发现欧拉函数的一个公式:
φ(n)=n*(1-1/p1)(1-1/p2)….(1-1/pk),其中p1、p2…pk为n的所有素因子。
比如:φ(12)=12*(1-1/2)(1-1/3)=4。
利用这个就比较好求了,可以用类似求素数的筛法。
先筛出N以内的所有素数,再以素数筛每个数的φ值。
比如求10以内所有数的φ值:
设一数组phi[11],赋初值phi[1]=1,phi[2]=2…phi[10]=10;
然后从2开始循环,把2的倍数的φ值*(1-1/2),则phi[2]=2*1/2=1,phi[4]=4*1/2=2,phi[6]=6*1/2=3….;
再是3,3的倍数的φ值*(1-1/3),则phi[3]=3*2/3=2,phi[6]=3*2/3=2,phi[9]=…..;
再5,再7…因为对每个素数都进行如此操作,因此任何一个n都得到了φ(n)=n*(1-1/p1)(1-1/p2)….(1-1/pk)的运算
觉得这个“筛”还是比较好用的,以前求数的所有因子之和也是用的它。

#include<stdio.h>
#include<string.h>
int phi[33000];
int gphi()
{
    int i,j;
    memset(phi,0,sizeof(phi));
    phi[1]=1;//与1互质的只有他本身一个 
    for(i=2;i<33000;i++)
       if(!phi[i])//因为在计算中j是以i在叠加的,所以所有被叠加到的数都是合数,所以当i
       //依次增加到那个数的时候发现那个数已经被赋值,表明那是个合数,无须再算,所以这里如果已经被赋值过了,就不能再进行计算了 
       //反之如果没被赋值,说明这个数肯定不是之前数的倍数,也就是i是质数,可以进行下面phi的计算 
           for(j=i;j<33000;j+=i)//这里重要的筛法,j+=i,表示以下出现的数,i都是j的因子 
           {
              if(!phi[j])phi[j]=j;//未赋值的时候,要先赋值为其本身 
              phi[j]=phi[j]/i*(i-1);//phi[j]=phi[j]*(1-1/i)会出现错误,因为1/i都变成0了 
           }
}
int main()
{
    int cn,n;
    gphi();
    scanf("%d",&cn);
    while(cn--&&scanf("%d",&n))
    printf("%d\n",phi[n]);
    return 0;
}

 


  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法