Chef and Prime Divisors Problem code: CHAPD （GCD问题）
题目大意：给定两个数，n,m，找到如果m的所有质因数可以被n,整处的话输出"Yes"，OR "No".
text:
3
120 75
128 16
7 8
Output:
Yes
Yes
No
直到，最大公约数为1，时看后者是否为1，即可。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<math.h>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
long long gcd(long long n,long long m)
{
returnm==0?n:gcd(m,n%m);//忘了加return WA了几次。。
}
int main()
{
long long n,m,cla;
cin>>cla;
while(cla--)
{
cin>>n>>m;
long long k=gcd(n,m);
while(k>1)
{
m=m/k;
k=gcd(n,m);
}
if(m==1)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
页:
[1]