

由题意可知只有操作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; }