CCF 1040. 除法游戏 (Standard IO)

时间限制: 1000 ms 空间限制: 262144 KB 具体限制

题目描述
小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;
}

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

我自己原来写的只有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;
}

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
 

文章来源: blog.csdn.net，作者：小生凡一，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_45304503/article/details/105214582