http://www.codechef.com/MAY15/problems/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 T test 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,判断A是否能被B的所有质因子整除。
思路:
所有数都可以看成是被很多的质数相乘,所以把B也看成这样的数,由于B和A的最大公约数一定能被A除,所以想到一直GCD处理B,如果最后B是1就说明整个B的因素都能被A整除
#include<iostream>
using namespace std;
long long gcd(long long a,long long b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
long long T;
cin >> T;
while(T--)
{
long long a,b;
cin >> a >> b;
long long num = gcd(a,b);
while(num>1)
{
b = b/num;
num = gcd(a,b);
}
if(b == 1)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
运维网声明
1、欢迎大家加入本站运维交流群:群②:261659950 群⑤:202807635 群⑦870801961 群⑧679858003
2、本站所有主题由该帖子作者发表,该帖子作者与运维网 享有帖子相关版权
3、所有作品的著作权均归原作者享有,请您和我们一样尊重他人的著作权等合法权益。如果您对作品感到满意,请购买正版
4、禁止制作、复制、发布和传播具有反动、淫秽、色情、暴力、凶杀等内容的信息,一经发现立即删除。若您因此触犯法律,一切后果自负,我们对此不承担任何责任
5、所有资源均系网友上传或者通过网络收集,我们仅提供一个展示、介绍、观摩学习的平台,我们不对其内容的准确性、可靠性、正当性、安全性、合法性等负责,亦不承担任何法律责任
6、所有作品仅供您个人学习、研究或欣赏,不得用于商业或者其他用途,否则,一切后果均由您自己承担,我们对此不承担任何法律责任
7、如涉及侵犯版权等问题,请您及时通知我们,我们将立即采取措施予以解决
8、联系人Email:admin@iyunv.com 网址:www.yunweiku.com