题解AT_abc142_d

· · 题解

原题链接

AtCoder 链接

题目大意：

给定两个数 a 和 b，问你可以选出多少个数使得每一个数都能整除 a 和 b，且数两两互质。

思路：

我们可以先算出 \gcd(a,b)，每一个满足要求的数都必然整除 \gcd(a,b)。显然，我们可以把 \gcd(a,b) 分解质因数，再把质因数个数加上 1，也就是选 1，最终输出。

下证这种情况是最优解：

假设有两个数 x 和 y，均能整除 \gcd(a,b)。如果现在有两个数 m 和 mn 可以选择，显然 \gcd(m,x) 整除 \gcd(mn,x)，所以选择 m 比选择 mn 好。

坑点：

  1. gcd 函数需要开 long long！
  2. 枚举质因数的时候循环变量要用 long long 或强制转换成 long long 类型，否则会炸精度！
  3. 不要忘记 1 也要选上！

上代码：

#include <iostream>
using namespace std;

long long gcd(const long long &x, const long long &y){// gcd 函数模板(坑点1：long long 类型）
    return (x % y == 0 ? y : gcd(y, x % y));
}

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);// cin、cout 加速
    long long a, b;
    cin >> a >> b;
    long long temp = gcd(a, b);
    int cnt = 0;
    // 分解质因数，统计质因数个数
    for (int i = 2; 1ll * i * i <= temp; i++){// 坑点 2：循环变量
        if (temp % i == 0){
            cnt++;
            while (temp % i == 0){
                temp /= i;
            }
        }
    }
    if (temp != 1){// 如果还有剩余的质因数，那么 cnt 再加上 1
        cnt++;
    }
    cout << cnt + 1 << "\n";// 坑点 3：1 也要算上
    return 0;
}