每日算法——互质个数和

关键词

欧拉定理

题目

定义 F(i) 表示 1 \backsim i 中与 i 互质的数的个数，现给定一个正整数 N，请你求出 \sum_2^NF(i)。

输入描述

第1行为一个整数 T，表示测试数据数量。

接下来的 T 行每行包含一个正整数 N。

1 \leq T \leq 10^5, 1 \leq N \leq 10^7。

输出描述

疏忽共 T 行，每行包含一个整数，表示答案。

示例

输入

5
1
2
3
4
5

输出

1
2
4
6
10

知识点¹

1. 欧拉函数

   欧拉函数 \varphi(n)(n \in N^*) 是小于等于 n 的正整数中与 n 互质的数的个数。

2. 欧拉定理

   对于任意互素的 a 和 n，有 a^{\varphi(n)} \equiv 1 (\mod n)

3. 欧拉函数求法
   \varphi(1) = 1。
   如果 n 是质数， 则 \varphi(n) = n - 1。
   如果 n = p^k(p 为质数,k \in N^*)，则 $\varphi(p^k) = p^k - p^{k-1}$。
   如果 n = p \cdot q ，而且 p, q 互质，有 \varphi(n) = \varphi(p \cdot q) = \varphi(p) \cdot \varphi (q)
   通式：\varphi(n) = n \displaystyle \sum_{i=1}^r(1 - \frac{1}{p_i} )，其中 n = p_1^{k_1} \cdot p_2^{k_2} ... p_r^{k_r}(p_1, ..., p_r都为质数)

解决方案

通式求欧拉数

int Euler(int n){
    if (n <= 1) return 0;
    int ret = n;
    int s = (int) sqrt(n);
    for (int i=2; i <= s; i++){
        if (n % i == 0){
            ret = ret - ret / i;
            while (n %  i == 0) {
                n = n / i;
            }
        }
    }
    if (n > 1) ret = ret - ret /n;
    return ret;
}

注：此算法仅为求解欧拉数的简便算法，并不保证是此题的最优算法

引用