Codeforces #680 Div1 A. Division

D解けてないのは残念。
http://codeforces.com/contest/1444/problem/A

問題

正整数P,Qが与えられる。
以下を満たす最大のXを求めよ。

• PはXで割り切れる
• XはQで割り切れない

解法

Pは大きいがQがさほど大きくないことに着目。

• PをQで割り切れないなら、X=P。
• そうでない場合、Qの素因数kに対し、P/k、P/(k^2)、P/(k^3)...と割ってみて、Qを割り切れないものがあれば解の候補としよう。

上記で順では、Qを素因数分解すればよいので、あまり時間がかからない。

int T;
ll P,Q;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>P>>Q;
		
		if(P%Q) {
			cout<<P<<endl;
			continue;
		}
		
		vector<int> C;
		ll V=Q;
		for(i=2;i*i<=V;i++) if(V%i==0) {
			C.push_back(i);
			while(V%i==0) V/=i;
		}
		if(V>1) C.push_back(V);
		
		ll ret=1;
		FORR(c,C) {
			ll a=P;
			while(a%Q==0) a/=c;
			ret=max(a,ret);
		}
		cout<<ret<<endl;
	}
	
}

まとめ

A問題の割に、本番地味に手間取った。