Chef and Prime Divisors（GCD）
点击打开链接https://www.codechef.com/problems/CHAPD
Chef and Prime Divisors
Problem code: CHAPD
You are given two positive integers – A and B. You have to check whether A is divisible by all the prime divisors of B.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of Ttest cases follows.
For each test case, you are given two space separated integers – A and B.
Output
For each test case, output "Yes" (without quotes) if A contains all prime divisors of B, otherwise print "No".
Constraints
[*]1 ≤ T ≤ 104
[*]1 ≤ A, B ≤ 1018
Subtasks
[*]Subtask 1 (20 points):1 ≤ B ≤ 107
[*]Subtask 2 (30 points):1 ≤ A ≤ 107
[*]Subtask 3 (50 points): Original constraints
Example
Input:
3
120 75
128 16
7 8
Output:
Yes
Yes
No
Explanation
Example case 1. In the first case 120 = 23*3*5 and 75 = 3*52. 120 is divisible by both 3 and 5. Hence, we will print "Yes"
Example case 2. In the second case both 128 and 16 are powers of two. Hence, the answer is "Yes"
Example case 3. In the third case 8 is power of two and 7 is not divisible by 2. So, the answer is "No"
题意： 问A能不能被B的所有质因数整除
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
using namespace std;
typedef unsigned long long ull;
ull gcd(ull a,ull b)
{
ull m=max(a,b);
ull n=min(a,b);
while(m%n!=0)
{
ull t=m;
m=n;
n=t%n;
}
return n;
}
int main()
{
ull a,b;
int T;
scanf("%d",&T);
while(T--)
{
scanf("%llu%llu",&a,&b);
if(b==1)
{
printf("Yes\n");
continue;
}
ull c=gcd(a,b);
bool fnd=0;
while(c!=1)
{
if(c==b)
{
fnd=1;
break;
}
b/=c;
c=gcd(a,b);
}
if(fnd)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
}
页:
[1]