从“最简真分数的个数”谈起

      所谓最简真分数是一个分数的分子小于分母，且分子分母无公因数。
      2010年湖北省小学奥林匹克数学竞赛（小学六年级组）有这样一道试题：以2010为分母的最简真分数有多少个？
      这道小学奥数试题考察的是学生对集合包含和容斥知识的掌握情况。
      由于2010=2*3*5*67（分解质因数），因此以2010为分母的最简真分数的分子必须小于2010且不能被2、3、5或67整除。
      小朋友解决这个问题的计算过程如下：
      在1~2010共2010个数中，
      能被2整除的数有 2010÷2=1005
      能被3整除的数有 2010÷3=670
      能被5整除的数有 2010÷5=402
      能被67整除的数有 2010÷67=30
      能同时被2和3整除的数有 2010÷（2×3）=335
      能同时被2和5整除的数有 2010÷（2×5）=201
      能同时被2和67整除的数有 2010÷（2×67）=15
      能同时被3和5整除的数有 2010÷（3×5）=134
      能同时被3和67整除的数有 2010÷（3×67）=10
      能同时被5和67整除的数有 2010÷（5×67）=6
      能同时被2、3和5整除的数有 2010÷（2×3×5）=67
      能同时被2、3和67整除的数有 2010÷（2×3×67）=5
      能同时被2、5和67整除的数有 2010÷（2×5×67）=3
      能同时被3、5和67整除的数有 2010÷（3×5×67）=2
      能同时被2、3、5和67整除的数有 2010÷（2×3×5×67）=1
      这样，1~2010中能被2或3或5或67整除的数有
        （1005+670+402+30）-（335+201+15+134+10+6）+（67+5+3+2）-1
       =2107-701+77-1   =1482
      因此，1~2010中既不能被2整除，也不能被3整除，也不能被5整除，也不能被67整除的数有 2010-1482=528 个。
      即以2010为分母的最简真分数有528个。

      我们可以看出，上面的计算过程是比较繁琐的，需要认真仔细。
      学习过程序设计后，可以编写了一个简单的循环程序解决这个问题。
      用一个变量cnt来保存最简真分数的个数，初始值为0。
      对1~2010中的每一个数num，进行判断，这是一个循环，写成
             for(num=1; num<=2010;num++)
      循环体中的判断方法为：如果num既不能被2整除，也不能被3整除，也不能被5整除，也不能被67整除，则计数。写成
       if(num%2!=0 && num%3!=0 && num%5!=0 && num %67!=0)
              cnt++;
      最后，输出结果cnt。   一个简单的程序，就得到问题的答案。
   编写的源程序如下：
       #include <stdio.h>
       int main()
       {
             int cnt,num;
             cnt=0;
             for (num=1; num<=2010;num++)
                  if (num%2!=0 && num%3!=0 && num%5!=0 && num %67!=0)
                       cnt++;
             printf("%d\n",cnt);
             return 0;
       }

      需要说明的是，当时竞赛的真题是：所有以2010为分母的最简真分数的和为多少？

      瞧瞧，作为大学生的你还能像小朋友一样做出来吗？

      当然，你学过程序设计，将上面的程序简单改写一下，可以很快得到答案的。何须像小朋友一样苦苦思考和运算呢。

#include <stdio.h>
int main()
{
     int num;
     double sum;
     sum=0;
     for (num=1; num<=2010;num++)
         if (num%2!=0 && num%3!=0 && num%5!=0 && num %67!=0)
               sum+=1.0*num/2010;
     printf("%lf\n",sum);
     return 0;
}

      程序运行后，输出 264.000000。即所有以2010为分母的最简真分数的和是264。

      小朋友是没法像程序一样硬算的。1/2010+7/2010+11/2010+…+2099/2010=264。

      小朋友有小朋友的聪明，1/2010是最简真分数，那么2099/2010 也一定是最简真分数。

      i/2010 是最简真分数，那么 （2010-i）/2010 也一定是最简真分数。

      1/2010 + 2099/2010=1         i/2010 +（2010-i）/2010=1。

      小朋友知道了以2010为分母的最简真分数有528个，因此它们的和为 528/2 = 264。

      因为2010分解质因数后，因数有2、3、5和67四个，用于考察集合的包含与容斥计算量略大但又可以完成，可以算是一道很好的竞赛试题。

     在这道试题的基础上，我们看这样一个问题。

【例1】最简真分数。

      任意输入一个正整数n，求以n为分母的最简真分数有多少个？

     （1）编程思路1。

      将输入的n作为分母，穷举分子i （1≤i≤n-1）。因此，程序可先写成如下的循环：

         for (i=1; i<=n-1; i++)
        {
               对每一分数i/n，进行是否存在公因数的检测。根据检测的结果决定是否计数；
        }
      在上面的循环体中需要对每一分数i/n，进行是否存在公因数的检测。如果分子i与分母n存在大于1的公因数k，说明i/n不是最简真分数，不予计数。怎样进行检测呢？
      因为公因数k的取值范围为[2，i]，因而设置u循环在[2，i]中穷举k，若满足条件
            i%k==0 && n%k==0
      说明分子分母存在公因数k，标记t=1后退出。
      在对因子k进行循环穷举前，可设置标志t=0。退出因子穷举循环后，若t=1，说明分子和分母存在公因子；若保持原t=0，说明分子分母无公因数，统计个数。

      （2）源程序1。

#include <stdio.h>
int main()
{
      int n,i,k,t,cnt;
      while (scanf("%d",&n) && n!=0)
      {
           cnt=0;
           for (i=1;i<=n-1;i++)       // 穷举分子
           {
                t=0;
                for (k=2;k<=i;k++)  // 穷举因数
                    if (i%k==0 && n%k==0)
                    {
                         t=1;
                         break;          // 分子分母有公因数舍去
                    }
               if (t==0)
                     cnt++;           // 统计最简真分数个数
          }
          printf("%d\n",cnt);
      }
      return 0;
}

      将上面的源程序提交给 poj 2407 “relatives”，判定为time limit exceeded。  poj 2407的题意是： 输入正整数n，求小于或等于n ([1,n])，且与n互质的正整数（包括1）的个数。这与求最简真分数的意思完全一致。

      上面源程序1的方法简单直接，但对于n值较大的话，会超时的。因此，我们应找到快速的求法。在数论中，欧拉函数就很好地解决了这样的问题。

      在数论，对于正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，一般简记为φ函数。 例如，φ(8)=4，因为1,3,5,7均和8互质。

      一般来说，设正整数n分解质因数后，n=p1^q1*p2^q2*...*pn^qn.

      则   φ(n)=n*(1-1/p1)*(1-1/p2)*...*(1-1/pn)。

      例如， 10= 2*5     φ(10)=10×(1-1/2)×(1-1/5)=4;     这4个数是1, 3, 7, 9 。

         30=2*3*5   φ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8;  这8个数是1,7,11,13, 17, 19, 23, 29。

       按欧拉函数的求法，可以编写如下的源程序。

      （3）源程序2。

#include <stdio.h>
int main()
{
      int n,i,j,ans,t;
      while (scanf("%d", &n) && n!=0)
      {
            ans = n;
            t=n;
            for (i=2;i*i<=t;i++)
                if (t % i == 0)                 // 找到一个质因数i
                 {
                      ans -= ans/i;
                      while (t % i == 0)    // 将质因数i全去掉
                               t /= i;
                 }
            if (t!=1) ans -= ans/t;
            printf("%d\n",ans);
      }
      return 0;
}

      将源程序2提交给 poj 2407， 可以accepted。

【例2】还是最简真分数。

      输入一个正整数n，求分母在指定区间[2，n]的最简真分数共有多少个？

      例如，输入5，输出应为 9。这9个最简真分数是 {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5} 。

      （1）编程思路。

      例1的源程序2可以求欧拉函数φ(n)的值。用一个循环求出 φ(2)+φ(3)+…+φ(n)的累加和，即得本题的输出。

      （2）源程序。

#include <stdio.h>
int main()
{
      int n,i,k,ans,t,sum;
      while (scanf("%d", &n) && n!=0)
      {
           sum=0;
           for (k=2;k<=n;k++)
           {
                 ans = k;
                 t=k;
                 for (i=2;i*i<=t;i++)
                     if (t % i == 0)              // 找到一个质因数i
                     {
                          ans -= ans/i;
                          while (t % i == 0)   // 将质因数i全去掉
                               t /= i;
                      }
                 if (t!=1) ans -= ans/t;
                 sum+=ans;
          }
          printf("%d\n",sum);
      }
      return 0;
}

      将此源程序提交给 poj 2478 “farey sequence”，被判定为time limit exceeded。poj 2478的题意是：求1~n的欧拉函数的和。

      因为，例1中是在 o(sqrt(n)) 的时间内求出一个数n的欧拉函数值。

      如果要求100000以内所有正整数的欧拉函数值，上面程序采用的方法的复杂度将高达o(n*sqrt(n))。因此，容易超时。

      下面我们寻求更快的求欧拉函数值的方法。

      我们知道，欧拉函数值  φ(n)=n*(1-1/p1)*(1-1/p2)....*(1-1/pk)，其中p1、p2…pk为n的所有质因子。即欧拉函数的值与其质因子有关。用筛法可以方便地求出n以内的所有质数。关于筛法及应用可以参阅本博客中的随笔 poj中和质数相关的三个例题（poj 2262、poj 2739、poj 3006）。

      那么我们能不能在筛法求质数的同时求出所有数的欧拉函数呢？可以采用如下的方法：

      用筛法一边筛出n以内的所有质数，一边以类似于筛法的思想用质数筛出每个数的欧拉函数φ值。

      这里，利用了欧拉函数的几个基本性质：

      ① 若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。 
      ② 当n是质数时，φ(n) = n-1。显然，因为n是质数，1~n-1均与n互质。 
      ③ 欧拉函数是积性函数——若m,n互质，φ(m*n)=φ(m)*φ(n) 。

      ④ 假设质数p能整除n，那么

          如果p还能整除n / p ,  φ(n)  = φ(n / p) * p;
          如果p不能整除n / p,   φ(n)  = φ(n / p) * (p - 1)。

      定义数组phi[n]，元素phi[i]表示正整数i的欧拉函数值φ(i)。

      定义数组vis[n]，元素vis[i]=true表示i在筛子中，vis[i]=false表示i不在筛子中，已被筛掉。初始时，vis数组的元素全置为true，表示全部放在筛子中。

     定义数组prime[n]，元素prime[i]的值为第i个质数。

      下面以求20以内所有质数及所有数的φ值为例，来描述筛法的使用。

      1） 从i=2开始循环， vis[2]==true，找到第一个质数2，prime[0]=2，质数个数pnum=1；同时，phi[2]=2-1=1。

      采用循环 for (j = 0; j < pnum && prime[j]*i <maxn; j++ ) 将筛子中2的各质数倍数筛掉，同时求得相应数的欧拉函数值。（注意这里与通常的筛法有改变，主要为了用质数筛出各数的欧拉函数值）。

      筛去 2*prime[0]=2*2=4，即 vis[4]=false； phi[4]=phi[2]*prime[0]=1*2=2；

      2）i++，进行下次循环， vis[3]==true，找到第2个质数，prime[1]=3，pnum=2，同时phi[3]=3-1=2。

     筛去 3*prime[0]=3*2=6 ，即vis[6]=false;  置phi[6]=phi[3]*(prime[0]-1)=2*1=2；

     筛去 3*prime[1]=3*3=9 ，即vis[9]=false;  置phi[9]=phi[3]*(prime[1])=2*3=6；

     3）i++，进行下次循环， vis[4]==false，4不是质数。

     筛去 4*prime[0]=4*2=8 ，即vis[8]=false;  置phi[8]=phi[4]*(prime[0])=2*2=4；

     筛去 4*prime[1]=4*3=12 ，即vis[12]=false;  置phi[12]=phi[4]*(prime[1]-1)=2*2=4； 

          与  φ(12)=12*(1-1/2)(1-1/3)=4   比较下 更容易理解。

         phi[12]=phi[4]*(prime[1]-1)=phi[2]*prime[0]*(prime[1]-1)=2*(1-1/2)*2*3*(1-1/3)。
      4）i++，进行下次循环， vis[5]==true，找到第3个质数，prime[2]=5，pnum=3，同时phi[5]=5-1=4。

     筛去 5*prime[0]=5*2=10 ，即vis[10]=false;  置phi[10]=phi[5]*(prime[0]-1)=4*1=4；

     筛去 5*prime[1]=5*3=15 ，即vis[15]=false;  置phi[15]=phi[5]*(prime[1]-1)=4*2=8；

     筛去 5*prime[2]=5*5=25 ，即vis[25]=false;   当然我们以20为例的话，25已超出，循环不会执行到。

      同理，6不是质数，筛去 6*2=12，置 phi[12]=phi[6]*(prime[0])= 2*2=4。

                                     筛去 6*3=18 ，置phi[18]=phi[6]*(prime[1])=2*3=6。

                 7是质数，置prime[3]=7,pnum=4, phi[7]=6。    

                                    筛去 7*2=14，置 phi[14]=phi[7]*(prime[0]-1)= 6*1=6。

          …… 

      （3）采用筛法思想的源程序。

#include <stdio.h>
#include <string.h>
#define maxn 1000005
int prime[maxn], pnum, phi[maxn];
__int64 num[maxn]={0};
bool vis[maxn];
int main()
{
      int n,i,j;
      memset(vis,true,sizeof(vis));
      // 下面程序段既求maxn以内的素数又求欧拉数。
      pnum=0;
      phi[1] = 1;
      for (i = 2; i < maxn; i++)
      {
             if (vis[i])   //  i是素数
             {  
                   prime[pnum++] = i;
                   phi[i] = i-1;
             }
             for (j = 0; j < pnum && prime[j]*i <maxn; j++ )
             {
                     vis[prime[j]*i] = false;
                     if (i % prime[j] == 0)
                     {
                           phi[i*prime[j]] = phi[i] * prime[j];
                           break;
                     }
                     else
                           phi[i*prime[j]] = phi[i] *(prime[j] - 1);
             }
       }
      for (i=2;i<maxn;i++)
      {
            num[i]=num[i-1]+phi[i];
      }
      while (scanf("%d", &n) && n!=0)
      {
            printf("%i64d\n",num[n]);
      }
      return 0;
}

      将用筛法思想改写的源程序提交给 poj 2478， 可以accepted。

      将上面的程序略作改动，可以顺便通过 hdu 2824 “the euler function”。