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