2706: Let's Solve Geometric Problems(幾何問題を解こう)
「幾何問題かよ、やる気無くすわ」って思ったら全然幾何もんじゃなかった件、しかもそんなに法則見つけるのも難しくなく、素因数分解の要領でなんとかなる。
ただ最初は全然TLEが取れずなんでだろうと思ったらi*i<=qのところをi<=qとしてたからだった、初歩的なミス
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; }