【CF1445C】Divison 題解

• 2020 年 11 月 1 日
• 筆記
• Codeforces, 題解

原題鏈接

題意簡介

給出兩個正整數 p 和 q，要求一個最大的 x 使 p 可被 x 整除，而 q 不可被 x 整除。

其中，\(1 \leq p \leq 10^{18} ; 2 \leq q \leq 10^9\)。

思路分析

對於 \(p\mod q \neq 0\) 的情形，顯然 x 最大為 p。

至於 \(p \equiv 0 \mod q\) 的情形，可以這樣考慮：

首先，我們不難發現 p 必然包含 q 的所有質因數，且 p 質因數分解後每個質因數的指數必定大於等於 q 的。

現在，我們希望 \(x \mod q \neq 0\) 。要求 x 最大，所以我們希望這個 x 可以儘可能地接近 p。

我們記：

\(p = A_1^{d_1} \times A_2^{d_2} \times … \times A_n^{d_n} \times R\)

\(q = A_1^{c_1} \times A_2^{c_2} \times … \times A_n^{c_n}\)

顯然地，要使 x 儘可能大，我們只需要通過除去某個數，把 p 的某個質因數的指數 \(d_i\) 調到恰好比 \(c_i\) 小就行了。

所以，我們只需要對 q 做質因數分解，順便求出 \(c_i,d_i\) 。

然後枚舉每個質因數，找到最小的 \(A_i^{d_i-c_1+1}\) ，答案就是 p 除以它了。

程式碼庫

#include <cstdio>
#include <cstring>
typedef long long ll;
const int N=1e5;
ll a[N],cc,cq[N],cp[N],aq[N],ap[N];
int main(){
    ll t; scanf("%lld",&t);
    while(t--){
        ll p,q,p1,q1; scanf("%lld%lld",&p,&q);
        if(p%q!=0){
            printf("%lld\n",p);
            continue;
        }
        p1=p; q1=q; cc=0;
        for(int i=2;i*i<=q;i++){
            if(q1%i==0){
            	//記得初始化
                a[++cc]=i; cq[cc]=cp[cc]=0; ap[cc]=aq[cc]=1;
                while(q1%i==0) q1/=i,cq[cc]++,aq[cc]*=i;
                while(p1%i==0) p1/=i,cp[cc]++,ap[cc]*=i;
            }
        }
        //不要忘了這一步
        if(q1>1){
            a[++cc]=q1;
            cq[cc]=cp[cc]=0; ap[cc]=aq[cc]=1;
            while(q1%a[cc]==0) q1/=a[cc],cq[cc]++,aq[cc]*=a[cc];
            while(p1%a[cc]==0) p1/=a[cc],cp[cc]++,ap[cc]*=a[cc];
        }
        ll minn=1e18;
        for(int i=1;i<=cc;i++){
            if(ap[i]/(aq[i]/a[i])<minn) minn=ap[i]/(aq[i]/a[i]);
        }
        printf("%lld\n",p/minn);
    }
    return 0;
}