题解AT_abc142_d
shaozhehan
2023-04-01 21:02:49
[原题链接](https://www.luogu.com.cn/problem/AT_abc142_d)
[AtCoder 链接](https://atcoder.jp/contests/abc142/tasks/abc142_d)
题目大意：
给定两个数 $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```！
1. 枚举质因数的时候循环变量要用 ```long long``` 或强制转换成 ```long long``` 类型，否则会炸精度！
1. 不要忘记 $1$ 也要选上！
上代码：
```cpp
#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;
}
```