题目描述
小A和小B是一对好朋友，他们的爱好是研究数字。学过除法之后，他们就发明了一个新游戏：两人各说一个数字分别为a和b，如果a能包含b的所有质数因子，那么A就获胜。但是当数字太大的时候，两个朋友的脑算速度就有点跟不上了。
现在，请你写个程序，来判断胜负吧：输入两个正整数，表示a和b（2≤a, b≤10 18）。如果a包含了b的所有质数因子，则输出“Yes”，否则输出“No”（输出时没有引号）。
输入
输入两个正整数a和b,中间用一个空格隔开。
输出
如果a包含了b的所有质数因子，则输出“Yes”，否则输出“No”（输出时没有引号）。
样例输入
输入1：
120 75
输入2：
7 8
样例输出
输出1：
Yes
输出2：
No
数据范围限制
2≤a, b≤10 18
这是在CCF上面100通过的代码
个人觉得这种方法是有问题的
需要判断y/a的质因子,如果y/a是质数才是对的！
可以试试
54 48
51 27
这两组数据测出来的就是错的
#include <stdio.h> int main(){ long long int a,b,c,x,y; scanf("%lld%lld",&a,&b); x=a;y=b; while (b){ c=a%b;a=b;b=c; //辗转相除法,不然会超时 } if (a==1) printf("No"); if(a>1) { if(x%(y/a)==0) printf("Yes"); else printf("No"); } return 0; }
我自己原来写的只有40分。。。没办法。。
#include <stdio.h> int prime(int n) { int i; if (n==1) return 0; else{ for(i=2;i*i<=n;i++) { if(n%i==0) { return 0; } } return 1; } } int main() { int a,b,c,i,j=0,l,k,d[100]={},d1[100]={0}; scanf("%d%d",&a,&b); for(i=1;i<=a;i++) { if((a%i==0)&&(prime(i))) { d[j]=i; j++; k=j; } }j=0; for(i=1;i<=b;i++) { if((b%i==0)&&(prime(i))) { d1[j]=i; j++; l=j; } } for(i=0;i<k;i++) { printf("%d ",d[i]); //将其中的打印出来，放上去之前可以删掉，只是为了分析而已 } printf("\n"); for(j=0;j<l;j++) { printf("%d ",d1[j]); //打印出来，放上去之前可以删掉，只是为了分析而已 } int flag=0; for(i=0;i<l;i++) { for(j=0;j<k;j++) { if(d1[i]==d[j]) { flag++; break; } } } if(flag==l) printf("Yes\n"); else printf("No\n"); return 0; }
