1078.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 42 行

#include"iostream.h"

int t[100],n;


int go(int i,long s,long a,long b)
{if(s==1)return 1;
if(i==n)return 0;
if(a%t[i]==0)if(go(i+1,s/t[i],a/t[i],b))return 1;
if(b%t[i]==0)if(go(i+1,s/t[i],a,b/t[i]))return 1;
if(go(i+1,s,a,b))return 1;
return 0;
}





int main()
{int i;long a,b,s;
while(1)
{cin>>a;if(cin.fail())break;
 cin>>b;
 if(a<b){a=a+b;b=a-b;a=a-b;}
  s=a*b;n=0;
 for(i=100;i>1;i--)
  if(s%i==0&&(a%i==0||b%i==0))t[n++]=i;	   
  
  if(!go(0,b,b,1)){cout<<a<<endl;continue;}
  if(!go(0,a,a,1)){cout<<b<<endl;continue;}
   if(go(0,s,a,b)==1)cout<<a<<endl;
 else cout<<b<<endl;

}


return 1;
}