欧拉函数就是求解1~n之间与n互质的数的个数

一、求单独n的欧拉函数

import java.util.*;

public class Main {

    static int n;
    public static void main (String[]args) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();

        while (n -- > 0) {
            int a = sc.nextInt();

            OLA(a);
        }

    }

    static void OLA(int a) {
        int res = a;

        for (int i = 2; i <= a / i; i++) {
            if (a % i == 0) {
                res = res / i * (i - 1);
                while (a % i == 0) {
                    a /= i;
                }
            }
        }
        if (a > 1) res = res / a * (a - 1);

        System.out.println(res);
    }
}

例题

对于f(n)想要求解所增加的个数，设n分块为i/n (i = [1, n)),先假定如果gcd(i, n) != 1就一定在n的前面出现过i/n(上下除去gcd(i, n))
证明：
首先有gcd(i, n) > 1,下面记gcd为g, 那么有n / g < n, i / g < i,因此i/n在f(n/g)的地i/g的位置出现了

对于本题
只需要求解gcd(i, n) == 1的情况,也就是求1~n之间与n互质的数的个数,欧拉函数求解即可

#include <iostream>
#define LL long long

using namespace std;

LL n;

int main()
{
  cin >> n;

  LL ans = n;

  for (int i = 2; i <= n / i; i++) {
    if (n % i == 0) {
      while (n % i == 0)
        n /= i;

      ans = ans * (i - 1) / i;
    }
  }

  if (n > 1) {
    ans = ans * (n - 1) / n;
  }

  cout << ans;

  return 0;
}

二、求解前n位的欧拉函数(前n项欧拉函数之和)

线性筛法求欧拉

/*
    变量解释：
    phi[i]：OL(n)
    primes[i]: 第i个素数
    st[i]: 是否为素数，true为否，false表示为素数
*/
    static void getOLs(int n) {
        phi[1] = 1;//特判
        for (int i = 2; i <= n; i++) {
            if (!st[i]) {
                phi[i] = i - 1;//i为素数，则1~i之间与i互素的个数为i - 1
                primes[idx ++] = i;
            }
            for (int j = 0; primes[j] <= n / i; j++) {
                int pj = primes[j];
                st[pj * i] = true;
                if (i % pj == 0) {//pj为i的最小质因子
                    /*
                    那么pj也是pj * i的最小质因子，因此(1 - 1 / pj)
                    这一项就已经在phi[i]中计算过了(因为pj是i的最小质因子)
                    因此只需要补齐基数即可，将N修正回来
                    */
                    phi[pj * i] = phi[i] * pj;
                    break;
                }
                /*
                这是pj不是i的最小质因子情况，那么pj是pj * i的最小质因子，这样phi[pj * i]
                就比phi[i]要多了基数的pj倍，还多了pj质因子的贡献：
                (1 - 1 / pj)
                也就是phi[pj * i] = phi[i] * pj / pj * (pj - 1);
                化简：
                */
                phi[pj * i] = phi[i] * (pj - 1);
            }
        }
    }