A - Division

题目链接

题意

找一个最大的x">xx，满足p % x==0 and x % q!=0">p % x ==0 and x % q ! = 0 

思路

质因数分解

• p % q != 0">p % q != 0， x=p">x=p
• p % q = 0">p % q = 0 , 那么p">p一定包含q">q的所有质因数分解的结果。

举例：

p=12  q=6">p=12  q=6
p=22∗31">p=2 * 2 * 3  q=21+31">q=2 * 3

要使p % q != 0">p % q != 0, 只要使 p">p 将质因数2">2降幂到0">0(也就是q的质因数2">2的次幂之下)，或者将3">3 的幂降到0">00。

所以，我们只需要枚举q">q的质因子, 找权值最小的，即为答案。

q">不要忘了q本身

代码

#include 
using namespace std;
typedef long long ll;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        ll a, b;
        cin >> a >> b;
        if (a % b != 0)
        {
            cout << a << endl;
            continue;
        }
        ll mas = 0;
        for (int i = 2; i * i <= b; i++)
        {
            if (b % i)
                continue;
            ll c = a;
            while (c % b == 0)
                c /= i;
            mas = max(mas, c);
            c = a;
            while (c % b == 0)
                c /= (b / i);
            mas = max(mas, c);
        }
        while (a % b == 0)
            a /= b;
        mas = max(mas, a);
        cout << mas << endl;
    }

    return 0;
}