题目描述

给你 $n$ 个整数 $x_1,x_2,x_3, …, x_n$，对于每一个 $x_i$，求出 $\varphi(x_i)$ （即 $x_i$ 的欧拉函数）的值。

样例

输入样例：

3
3
6
8

输出样例：

2
2
4

思路

欧拉函数的定义：$1\sim x$ 当中与 $x$ 互质的数的个数被称为欧拉函数，记作 $\varphi(x)$.

若在算数基本定理中，$x=p_1^{r_1}p_2^{r_2}…p_m^{r_m}$，则有 $\varphi(x)=x\times \dfrac{p_1-1}{p_1}\times \dfrac{p_2-1}{p_2}\times …\times \dfrac{p_m-1}{p_m}=x\times \prod_{质数p|x}\left ( 1-\dfrac{1}{p} \right ) $.

证明：

设 $p$ 是 $x$ 的质因子，则 $1\sim x$ 中 $p$ 的倍数有 $p,2p,3p,…, \dfrac{x}{p} \times p$，共 $\dfrac{x}{p}$ 个。同理，若 $q$ 也是 $x$ 的质因子，则 $1\sim x$ 中 $q$ 的倍数有 $\dfrac{x}{q}$ 个。如果我们去掉这 $\left (\dfrac{x}{p}+\dfrac{x}{q}\right)$ 个数，那么 $pq$ 的倍数就会被除掉两次，需要再加回来一次（容斥原理）。

所以，$1\sim x$ 中不含有质因子 $p,q$ 的数的个数为 $\left(x-\dfrac{x}{p}-\dfrac{x}{q}+\dfrac{x}{pq}\right)$.

同理，通过对 $x$ 的所有质因数进行容斥，即可得到 $\varphi(x)=x\times \dfrac{p_1-1}{p_1}\times \dfrac{p_2-1}{p_2}\times …\times \dfrac{p_m-1}{p_m}=x\times \prod_{质数p|x}\left ( 1-\dfrac{1}{p} \right ) $.

代码

根据刚才我们推出来的公式，并结合判断质因数的代码，我们可以写出计算欧拉函数的代码。

需要注意的是，公式中的 $\varphi(x)=x\times \dfrac{p_1-1}{p_1}\times \dfrac{p_2-1}{p_2}\times …\times \dfrac{p_m-1}{p_m}$ 不能直接套用，否则会导致浮点误差。我们可以定义变量 $e$ 存储结果，并将其初始化为 $x$. 对于 $x$ 的每一个质因数 $p$，$e\leftarrow e\times \left ( 1-\dfrac{1}{p} \right ) =\dfrac{e}{p}\times (p-1)$ . 最后直接输出 $e$ 即可。

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    while (n --) {
        int x;
        scanf("%d", &x);

        int euler = x;
        for (int i = 2; i <= x/i; ++i) {
            if (x % i == 0) {
                euler = euler / i * (i-1);
                while (x % i == 0)
                    x /= i;
            }
        }
        if (x != 1)
            euler = euler / x * (x-1);
        printf("%d\n", euler);
    }
    return 0;
}

#include <iostream>
#include <cstdio>

using namespace std;

int gcd(int a, int b) {
    if (a % b == 0)
        return b;
    else
        return gcd(b, a%b);
}

int main() {
    int n;
    scanf("%d", &n);
    while (n --) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", gcd(a, b));
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <unordered_map>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

int main() {
    int n;
    scanf("%d", &n);

    unordered_map<int, int> prime;

    while (n --) {
        int x;
        scanf("%d", &x);

        for (int i = 2; i <= x/i; ++i) {
            while (x % i == 0)
                x /= i, prime[i] ++;
        }
        if (x > 1)
            prime[x] ++;
    }

    ll res = 1;
    for (auto i : prime) {
        ll p = i.first, r = i.second;
        ll t = 1;
        while (r --) 
            t = (p * t + 1) % mod;
        res = res * t % mod;
    }

    printf("%lld", res);

    return 0;
}

题目描述

给你 $n$ 个数 $a_1,a_2,a_3,…,a_n$，求出这 $n$ 个数的积的因数个数对 $10^9+7$ 取模的结果。

样例

输入样例1：

3
2
6
8

输出样例1：

252

算法分析

首先我们需要知道一个小学奥数的知识：

如果正整数 $n=p_1^{r_1}p_2^{r_2}p_3^{r_3}…p_k^{r_k}$（其中 $p_i$ 均为质数，$r_i$ 均为大于等于 $1$ 的正整数），那么 $n$ 的所有因数之和是 $\prod_{i=1}^{k}\sum_{j=0}^{r_i}p_i^j=(1+p_1+p_1^2+…+p_1^{r_1})(1+p_2+p_2^2+…+p_2^{r_2})…(1+p_k+p_k^2$$+…+p_k^{r_k})$.

但由于这 $n$ 个数的积可能过大，所以我们可以用与 870 约数个数 中相同的办法，先统计出 $a_i$ 的质因数，最后再把它们计算出来。

unordered_map<int, int> prime;

while (n --) {
    int x;
    scanf("%d", &x);

    for (int i = 2; i <= x/i; ++i) {
        while (x % i == 0)
            x /= i, prime[i] ++;
    }
    if (x > 1)
        prime[x] ++;
}

然后我们定义一个 int 类型的变量 $res$ 储存结果。然后对于每一个质因数 $p_i$，我们需要计算出 $\sum_{j=0}^{r_i}p_i^j=1+p_i+p_i^2+…+p_i^{r_j}$. 我们可以采用一个巧妙的计算方法：

1. 定义一个临时变量 $t$，储存 $\sum_{j=0}^{r_i}p_i^j$ 的结果，并将其初始化为 $1$.
2. 将 $t$ 乘上 $p_i$ 并加上 $1$，此时 $t=p_i+1$.
3. 再将 $t$ 乘上 $p_1$ 并加上 $1$，此时 $t=P-i(p_i+1)+1=p_i^2+p_i+1$.

这样重复 $r_i$ 次，就可以得到结果了。最后将 $res$ 加上 $t$ 即可。

ll res = 1;
for (auto i : prime) {
    ll p = i.first, r = i.second;
    ll t = 1;
    while (r --) 
        t = (p * t + 1) % mod;
    res = res * t % mod;
}

完整代码

#include <iostream>
#include <cstdio>
#include <unordered_map>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

int main() {
    int n;
    scanf("%d", &n);

    unordered_map<int, int> prime;

    while (n --) {
        int x;
        scanf("%d", &x);

        for (int i = 2; i <= x/i; ++i) {
            while (x % i == 0)
                x /= i, prime[i] ++;
        }
        if (x > 1)
            prime[x] ++;
    }

    ll res = 1;
    for (auto i : prime) {
        ll p = i.first, r = i.second;
        ll t = 1;
        while (r --) 
            t = (p * t + 1) % mod;
        res = res * t % mod;
    }

    printf("%lld", res);

    return 0;
}

#include <iostream>
#include <cstdio>
#include <unordered_map>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

int main() {
    int n;
    scanf("%d", &n);

    unordered_map<int, int> prime;

    while (n --) {
        int x;
        scanf("%d", &x);
        for (int i = 2; i <= x/i; ++i) {
            while (x % i == 0) 
                prime[i] ++, x /= i;
        }
        if (x > 1)
            prime[x] ++;
    }

    ll res = 1;
    for (auto i : prime) 
        res = res * (i.second+1) % mod;

    printf("%lld", res);

    return 0;
}

题目描述

给你 $n$ 个正整数 $a_1,a_2,a_3,…,a_n$，求 $a_1\times a_2\times a_3\times … \times a_n$ 的因数个数对 $10^9+7$ 取模的结果。

样例

输入样例1：

3
2
6
8

输出样例1：

12

算法

首先我们需要知道一个小学奥数知识：

如果一个正整数 $n$ 可被分解为 $p_1^{r_1}p_2^{r_2}p_3^{r_3}…p_k^{r_k}$（其中 $p_1,p_2,p_3,…,p_k$ 均为质数，$r_1,r_2,r_3,…,r_k$ 为大于等于 $1$ 的正整数），那么 $n$ 的因数个数为 $(r_1+1)(r_2+1)(r_3+1)…(r_k+1)$.

但是因为 $a_1\times a_2\times a_3\times … \times a_n$ 的结果可能过大，所以我们可以先统计出每一个 $a_i$ 的质因数个数，最后把它们加起来即可。

（详情见 867 分解质因数 题解）

#include <iostream>
#include <cstdio>
#include <unordered_map> //用哈希表存储质数

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

int main() {
    int n;
    scanf("%d", &n);

    unordered_map<int, int> prime;

    while (n --) {
        int x;
        scanf("%d", &x);
        for (int i = 2; i <= x/i; ++i) { //分解质因数
            while (x % i == 0) 
                prime[i] ++, x /= i;
        }
        if (x > 1)
            prime[x] ++; 
    }

    ll res = 1;
    for (auto i : prime) 
        res = res * (i.second+1) % mod;
        //运用公式计算，注意每次算完都要取模，否则可能溢出

    printf("%lld", res);

    return 0;
}

题目描述

给你 $n$ 个正整数 $a_1,a_2,a_3,…,a_n$，求 $a_1\times a_2\times a_3\times … \times a_n$ 的因数个数对 $10^9+7$ 取模的结果。

样例

输入样例1：

3
2
6
8

输出样例1：

12

算法

首先我们需要知道一个小学奥数知识：

如果一个正整数 $n$ 可被分解为 $p_1^{r_1}p_2^{r_2}p_3^{r_3}…p_k^{r_k}$（其中 $p_1,p_2,p_3,…,p_k$ 均为质数，$r_1,r_2,r_3,…,r_k$ 为大于等于 $1$ 的正整数），那么 $n$ 的因数个数为 $(r_1+1)(r_2+1)(r_3+1)…(r_k+1)$.

但是因为 $a_1\times a_2\times a_3\times … \times a_n$ 的结果可能过大，所以我们可以先统计出每一个 $a_i$ 的质因数个数，最后把它们加起来即可。

（详情见 867 分解质因数 题解）

#include <iostream>
#include <cstdio>
#include <unordered_map> //用哈希表存储质数

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

int main() {
    int n;
    scanf("%d", &n);

    unordered_map<int, int> prime;

    while (n --) {
        int x;
        scanf("%d", &x);
        for (int i = 2; i <= x/i; ++i) { //分解质因数
            while (x % i == 0) 
                prime[i] ++, x /= i;
        }
        if (x > 1)
            prime[x] ++; 
    }

    ll res = 1;
    for (auto i : prime) 
        res = res * (i.second+1) % mod; //运用公式计算，注意每次算完都要取模，否则可能溢出

    printf("%lld", res);

    return 0;
}

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e5+5;

int fac[N];

int main() {
    int n;
    scanf("%d", &n);
    while (n --) {
        int t;
        scanf("%d", &t);
        int cnt = 0;
        for (int i = 1; i <= t/i; ++i) {
            if (t % i == 0) {
                printf("%d ", i);
                fac[cnt ++] = i;
            }
        }
        for (int i = cnt-1; i >= 0; --i) {
            if (fac[i] != t/fac[i])
                printf("%d ", t/fac[i]);
        }
        printf("\n");
    }
    return 0;
}

题目描述

给你 $n$ 个正整数 $a_1,a_2,a_3,…,a_n$，求出它们的所有因数。

样例

输入样例1：

2
6
8

输出样例1：

1 2 3 6
1 2 4 8

算法

这一个是 y 总的方法。

可以证明：对于任意正整数 $n,d$，若 $d|n$，则有 $\dfrac{n}{d}|n$，所以我们只需要枚举到 $\sqrt{n}$ 即可。

我们可以用一个 vector 类型数组 $res$ 来存储 $n$ 的约数。对于小于等于 $\sqrt{n}$ 的 正整数 $i$，若 $n$ 能被 $i$ 整除，则将 $i$ 加入 $res$. 如果 $i\neq \sqrt{n}$，则将 $\dfrac{n}{i}$ 也加入 $res$ 中。最后对 $res$ 进行排序即可。

算法实现如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    while (t --) {
        int n;
        scanf("%d", &n);
        vector<int> res;
        for (int i = 1; i <= n/i; ++i) {
            if (n % i == 0) {
                res.push_back(i);
                if (i != n/i)
                    res.push_back(n/i);
            }
        }
        sort(res.begin(), res.end());
        for (int i = 0; i < res.size(); ++i) 
            printf("%d ", res[i]);
        puts("");
    }
    return 0;
}

但这个算法最后还要进行一次排序，最快是在 $90\text{ms}$ 上下波动，主要原因是最后的 sort 浪费了时间。

那么我们可以换一种方式：先求出所有小于等于 $\sqrt{n}$ 的 $n$ 的因数，把它们都存在一个数组 $fac$ 中。再从后向前遍历 $fac$，当 $fac_i$ 不等于 $\sqrt{n}$ 时就将 $\dfrac{n}{i}$ 添加进 $fac$，这样就避免了最后的排序，最快在 $80\text{ms}$ 左右。

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e5+5;

int fac[N];

int main() {
    int n;
    scanf("%d", &n);
    while (n --) {
        int t;
        scanf("%d", &t);
        int cnt = 0;
        for (int i = 1; i <= t/i; ++i) {
            if (t % i == 0) {
                printf("%d ", i);
                fac[cnt ++] = i;
            }
        }
        for (int i = cnt-1; i >= 0; --i) {
            if (fac[i] != t/fac[i])
                printf("%d ", t/fac[i]);
        }
        printf("\n");
    }
    return 0;
}