题目翻译

给定两个数 $a$ 和 $b$ ，求能同时整除 $a$ 和 $b$ 的数的个数，且这些数需要两两互质。

题目分析

两两互质，也就说明有以下几种情况：

1. 均为不同的质数。
2. 相邻 。
3. 一个是质数，另一个不是他的倍数。
4. 所有数和 $1$。
5. 相邻奇数
6. 较大数是质数。
   ……

这是常见的情况，其实还有很多。那么我们肯定不能全写到程序里。我们只选择第 $1$ 个性质：均为不同的质数。

确保了找的答案是质数，然后确保它是这两个数的因数（因为能整除），那么我们只要找到两个数共同的质因数。

共同的质因数，一定是两个数最大公因数的质因数。

所以找出最大公因数，再找出所有最大公因数的质因数（还要算上特殊的"1"），即为答案。

题目代码

#include<bits/stdc++.h>
#define ll long long//数据很大，要long long
using namespace std;
ll a,b,s=1;//1一定是两个数的公因数
ll gcd(ll x,ll y)
{
    return y?gcd(y,x%y):x;//辗转相除法求最大公因数
}
int main()
{
    cin>>a>>b;
    ll g=gcd(a,b);
    for(ll i=2;i<=sqrt(g);i++)//枚举最大公因数的质因数
    {
        if(g%i==0)//如果是的（后续补充说明）
        {
            s++;//找到了一个
            while(g%i==0)g/=i;//把这个质因数除完
        }
    }
    cout<<(g!=1?++s:s);//如果有剩余的质因数，再加上1
}

补充说明

第 $15$ 行 if(g%i==0) 解释

找到了$g$ 最小能整除的数 $i$，那么 $i$ 肯定是个质数，不用加以判断。

举个不成功的反例验证一下结论。

如果 $i$ 不是质数，说明 $i$ 还有其他因数，那么 $i$ 的因数也就是 $g$ 的因数了，$i$ 肯定不是最小能被整除的数了。

所以得出结论，$i$ 肯定是个质数，不用加上质数判断。