K.史莱尼克号(ACM实验室新生赛)

由题意可知只有操作2是减小总重量的,而操作1,3是a,b交换因子,所以a*b的偶数个因子都可以除掉,最后剩下的就是答案。

#include<cstdio>
#include<iostream>
using namespace std;
 int n,m;
 int a[10]={};
 int gcd(int a,int b)
 {
     return b==0?a:gcd(b,a%b);
 }
 int main()
 {
     int x,y;
     cin>>n;
     while(n--)
     {
         cin>>x>>y;
         if(x<y)
         {
             int t=x;
             x=y;
             y=t;
         }
         int k=gcd(x,y);
         x/=k;
         y/=k;
         int t=x*y;
    for(int i=2;i<=x;i++)     
    {        while(t%(i*i)==0)
             {
                 t/=(i*i);
     //            cout<<t<<" +++++ " <<i<<endl;
             }
         }
         cout<<t<<endl;
     }
     return 0;
 }
 

发表回复