andyli

题解 CF1203C 【Common Divisors】
先求出所有数字的最大公约数$x$,然后通过分解质因数的方法来计算$x$的约数个数。如何用分解质因数的方法计算某个数...
扫描右侧二维码阅读全文
14
2019/08

题解 CF1203C 【Common Divisors】

先求出所有数字的最大公约数$x$,然后通过分解质因数的方法来计算$x$的约数个数。
如何用分解质因数的方法计算某个数的约数个数呢?
假设我们需要求$216$这个数字的因数个数,分解质因数后得到:
$$216=2^3*3^3$$

对于2这个质数有4种选法:$2^0,2^1,2^2,2^3$,3也有4种选法:$3^0,3^1,3^2,3^3$,所以216的因数个数就是$4\times4=16$.

既然明白了这个道理,就可以轻松编写出程序了,注意使用$long long$。代码如下:

#include <cmath>
#include <cstdio>
#include <numeric>
using namespace std;
const int maxn = 400005;

long long A[maxn];
bool isprime(long long n) // 判断质数
{
    if (n <= 1)
        return false;
    int m = sqrt(n) + 0.5;
    for (int i = 2; i <= m; i++)
        if (n % i == 0)
            return false;
    return true;
}
int main()
{
    int n;
    scanf("%d%lld", &n, &A[1]);
    long long x = A[1];
    for (int i = 2; i <= n; i++)
        scanf("%lld", &A[i]), x = gcd(x, A[i]); // <numeric>头文件中在C++17标准里内置了gcd函数
    long long ans = 1;
    for (long long i = 2; i * i <= x; i++) { // 将x分解质因数并计算ans
        if (isprime(i)) {
            int cnt = 0;
            while (x % i == 0)
                x /= i, cnt++;
            ans *= (cnt + 1);
        }
    }
    printf("%lld\n", x > 1 ? (ans << 1) : ans); // 输出答案
    return 0;
}
Last modification:November 23rd, 2019 at 11:16 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment