CCF 1040. 除法遊戲 (Standard IO)

題目描述

小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;
}