2700: Airport Codes(空港コード)
それぞれの文字列に対してkにおける操作をして、setで管理したらなぜか通った。setの計算量が未だによくわかってないのに乱用していて良くない。
int gcd(int a,int b){ if(b==0)return a; return gcd(b,a%b); } int main(){ int p,q; cin>>p>>q; int r=gcd(q,p); p/=r;q/=r; int ans=1; for(int i=2;i*i<=q;i++){ if(q%i!=0)continue; ans*=i; while(q%i==0)q/=i; } ans*=q; cout<<ans<<endl; }