算法分析

题目问题，有多少对(x,b)，使得gcd(x,y) = p，其中p是质数

等价于gcd(x / p,y / p) = 1,等价于存在多少对(x,y)，x % p == 0且y % p == 0,时，x / p 和y / p 互质，等价于对于每个质数p，在1到n / p中，存在多少对(x,y)互质

算出对于每个质数p，从1到n / p 的欧拉函数的总和$res = \sum 2 * (\varphi(2) + \varphi(3) + … + \varphi(n / p))+ 1$

时间复杂度 $O(n)$

参考文献

算法提高课

Java 代码

import java.util.Scanner;

public class Main {
    static int N = 10000010;
    static int[] primes = new int[N];
    static boolean[] st = new boolean[N];
    static int cnt = 0;
    static int[] phi = new int[N];
    static long[] s = new long[N];
    static void init(int n)
    {
        for(int i = 2;i <= n;i ++)
        {
            if(!st[i]) 
            {
                primes[cnt ++] = i;
                phi[i] = i - 1;
            }
            for(int j = 0;primes[j] * i <= n;j ++)
            {
                st[primes[j] * i] = true;
                if(i % primes[j] == 0)
                {
                    phi[primes[j] * i] = primes[j] * phi[i];
                    break;
                }
                phi[primes[j] * i] = (primes[j] - 1) * phi[i];
            }
        }
        for(int i = 1;i < n;i ++) s[i] = s[i - 1] + phi[i];
    }
    public static void main(String[] args)  {
       Scanner scan = new Scanner(System.in);
       int n = scan.nextInt();
       init(n);
       long res = 0;
       for(int i = 0;i < cnt;i ++)
       {
           res += s[n / primes[i]] * 2 + 1;
       }
       System.out.println(res);
    }
}