Codeforces 1445C Division

連結

http://codeforces.com/contest/1445/problem/C

題目大意

一共t組資料，每組資料

給你兩個整數p，q，找出一個最大的整數x，使得 p能整除x，x不能整除q。

（即： p % x ==0 , x % q != 0 ）

輸入輸出

Input

3

10 4

12 6

179 822

Output

10

4

179

資料範圍

1<=t<=50, 1<=p<=1e18,1<=q<=1e9

思路

顯然，當 p與q不滿足整除關系（p%q != 0) 時，最大的x就是p本身，這個簡單。

但是當 p % q == 0 時怎麼辦呢？

不難發現，當 p % q == 0 時，

我們令 q = A * B ，

則 p = An * Bn * C , 其中C是一個與A，B均不滿足整除關系的整數。

那麼，從每一個 x = p / An 中找到的x(max)不就是結果了嗎？

顯然，A、B的集合就是q的所有因子，我們隻需要O（sqrt（n))的時間來找出它們。

對于An,我們隻需要讓p不斷的除以因子A直到p不再能被q整除就行了。

example：

6 = 2 * 3；

6 = 1 * 6;

168 = 23 * 31 * 7;

168 = 11 *61 * 28;

PS： 上一次更新啊，那是一年前的事兒了~~~~

代碼：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll p,q;
ll ans = 0;
ll solve(ll x){
   if(x==1)
   return x;
	ll t=p;
    while(t%q==0)
	t/=x;
    return t;
}
void pre (ll x)
{
	for(ll i=1;i*i<=x;i++){
    	if(x%i==0) 
        {
        	ll a=i,b=x/i;
            ans = max(ans,solve(a));
			ans = max(ans,solve(b));
        }
    }
}
int main(){
	int t;
	cin>>t;
	while(t--){
		ans = 0;
		scanf("%lld %lld",&p,&q);
		pre(q); 
		if(ans!=0)
		printf("%lld\n",ans);
		else 
		printf("1\n");
	}
	return 0;
}