记一道数学作业

发表于 | 分类于 |

  1. 题目描述

    求小于 $ 120 $ 且与 $ 120 $ 互质的正整数个数。

  2. 做法

    1. 普通做法

      将 $ 120 $ 分解质因数，可发现 $ 120=2^{3}\times3\times5 $。

      设 $A=\left{x|(2|x)且x\le120\right}$,$ B=\left{x|(3|x)且x\le120\right} $,$ C=\left{x|(5|x)且x\le120\right} $。

      则 $ |A|=59 $ $ |B|=39 $

      则小于 $ 120 $ 的正整数中，与 $ 120 $ 不互质的个数为 $ | A \cup B \cup C | $ 。

      由容斥原理可知。。。（略）

    2. 文艺做法

      由题意可知，要求 $ \varphi(120) $ 。

      将 $ 120 $ 分解质因数，$ 120=2^{3} \times 3 \times 5 $。

      所以 $ \varphi(120)=120 \times \left(1-\frac{1}{2}\right) \times \left(1-\frac{1}{3}\right) \times \left(1-\frac{1}{5}\right) $

    3. 智障做法

      由莫比乌斯反演，可知 $ \varphi= \mu \times id $

      所以 $ \varphi=\sum_{d|120}^{120} \mu(d) \times id(\frac{120}{d}) $

      带值，求出 $ \varphi(120) $

    4. OI做法

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      void init()
      {
          phi[1]=sum[1]=1;
          for(int i=2;i<=siz;i++)
          {
              if(!vis[i])
              {
                  prime[++vnum]=i;
                  phi[i]=i-1;
              }
              for(int j=1;j<=vnum&&prime[j]*i<=siz;j++)
              {
                  vis[prime[j]*i]=1;
                  if(!(i%prime[j]))
                  {
                      phi[prime[j]*i]=phi[i]*prime[j];
                      break;
                  }
                  else phi[prime[j]*i]=phi[i]*phi[prime[j]];
              }
          }
          for(int i=1;i<=siz;i++)
              (sum[i]=sum[i-1]+phi[i])%=P;
      }