D - Disjoint Set of Common Divisors
Problem Statement
Given are positive integers AA and BB.
Let us choose some number of positive common divisors of AA and BB.
Here, any two of the chosen divisors must be coprime.
At most, how many divisors can we choose?
Definition of common divisorDefinition of being coprimeDefinition of dividing
Constraints
- All values in input are integers.
- 1≤A,B≤10121≤A,B≤1012
Input
Input is given from Standard Input in the following format:
AA BB
Output
Print the maximum number of divisors that can be chosen to satisfy the condition.
Sample Input 1 Copy
12 18
Sample Output 1 Copy
3
1212 and 1818 have the following positive common divisors: 11, 22, 33, and 66.
11 and 22 are coprime, 22 and 33 are coprime, and 33 and 11 are coprime, so we can choose 11, 22, and 33, which achieve the maximum result.
Sample Input 2 Copy
420 660
Sample Output 2 Copy
4
Sample Input 3 Copy
1 2019
Sample Output 3 Copy
1
11 and 20192019 have no positive common divisors other than 1
思路：找出有多少个公因子，并且公因子必须是素数。然后再加一。【比赛时思路一模一样，代码写挫了QAQ】
AC代码：
#include<bits/stdc++.h> using namespace std; #define int long long
bool isprime(int num){ // 判断是否是素数
if(num==){
return false;
}
if(num==)
return true;
if(num%==)
return false;
double sqrtNum = sqrt(num);
for (int i = ; i <= sqrtNum; i += )
{
if (num % i == )
{
return false;
}
}
return true;
}
vector<int> v;
signed main(){
int n,m;
cin>>n>>m;
int temp=min(n,m);
for(int i=;i*i<=temp;i++){ // 求一个数的因子的模板
if(temp%i==){
v.push_back(i);
if(i*i!=temp){
v.push_back(temp/i);
}
}
}
int ans=;
int t=max(n,m);
for(int i=;i<v.size();i++){
if(t%v[i]==&&isprime(v[i]))
ans++;
}
cout<<ans+;
return ;
}