题目大意:
找出A,B中的所有互质的因数。
解题思路:
首先,我们必须找出因数。我们知道对gcd(a,b)进行因数分解就能得到a,b的所有因数。但是这里需要互质的因数,所以我们这里需要对gcd(a,b)作质因数分解。质因数分解和因数分解的代码很像,不过有一些不同
if(res%i!=0)ans++; //得到一个因数后,我们ans++
while(res%i==0)res/=i //后面有这句话
if(res>2)ans++ //最后还有一个质因子的话需要再++
#include <bits/stdc++.h>
#define int long long
const int MAXN = 1e6 + 10;
using namespace std;
int prime[MAXN];
int Mark[MAXN];
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
bool isPrime(int n)
{
if (n <= 1) return false;
if (n <= 3) return true;
if (n%2 == 0 || n%3 == 0) return false;
for (int i=5; i*i<=n; i=i+6)
if (n%i == 0 || n%(i+2) == 0)
return false;
return true;
}
int32_t main() {
int a, b;cin >> a >> b;
int res=gcd(a,b);
int ans=0;
for(int i=2;i<=sqrt(res);i++){
if(res%i==0){
ans++;
while(res%i==0)res/=i;
}
}
if(res>2)ans++;
cout<<ans+1<<endl;
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)