D - Disjoint Set of Common Divisors

https://atcoder.jp/contests/abc142/tasks/abc142_d

题意

求满足互素条件下的A和B的因子最多有几个

 

思路:

分解gcd(A,B)的质因子,再加上1;

#include <iostream>
#include<algorithm>
#include<string>
using namespace std;
const int maxn =1e5+10;
long long gcd(long long x,long long y)
{
    if(y==0)return x;
    return gcd(y,x%y);
}
int main()
{
    long long x,y;
    cin >> x >> y;
    long long g=gcd(x,y);
    long long ans=0;
    for(long long i=2;i<= g / i; i++)
    {
        if(g%i==0)
        {
            ans++;
            while(g%i==0) g/=i;
        }
    }
    if(g>1) ans++;
    cout << ans +1 <<endl;
    return 0;
}

 

上一篇:CF1025F Disjoint Triangles 题解


下一篇:[poj]3280 Cheapest Palindrome 题解