Codeforces Round #680 (Div. 2, based on Moscow Team Olympiad) C. Division (数学)

题意:有两个数\(p\)和\(q\),找到一个最大的数\(x\),使得\(p\ mod\ x=0\)并且\(x\ mod\ q\ne 0\).
题解:首先,如果\(p\ mod\ q\ne0\),那么我们可以让\(x=p\)就行了,否则,就意味着,\(p\)可以被\(q\)整除,也就是说\(p\)的质因子包含了\(q\)的所有质因子,我们可以对\(q\)进行质因子分解,我们要求的\(x\)不能包含\(q\)的所有质因子(带次数),然后可以去枚举\(q\)的质因子,我们要让\(p\)的质因子不包含\(q\)的所有质因子,最佳的方法是,将\(p\)中与\(q\)枚举到的质因子的次数变为\(q\)中枚举的减一即可,因为这样\(p\)中与\(q\)相同的质因子次数比\(q\)的小,必然不能被\(q\)整除,那么我们就可以让\(x\)为现在的\(p\).

代码:

int t;

ll p,q;

ll fpow(ll a,ll k){

    ll res=1;

    while(k){

        if(k&1) res=res*a;

        k>>=1;

        a*=a;

    }

    return res;

}

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>t;

    while(t--){

        cin>>p>>q;

        ll ans=0;

        if(p%q!=0){

            cout<<p<<'\n';

            continue;

        }

        ll cur=q;

        for(ll i=2;i*i<=cur;++i){

            ll cnt=0;

            if(q%i==0){

                while(q%i==0){q/=i;cnt++;}

                ll tmp=p;

                while(tmp%i==0){tmp/=i;}

                ans=max(ans,tmp*fpow(i,cnt-1));

            }

        }

        if(q>1){

            ll tmp=p;

            while(tmp%q==0) tmp/=q;

            ans=max(ans,tmp);

        }

        cout<<ans<<'\n';

    }

    return 0;

}

巴特西

Codeforces Round #680 (Div. 2, based on Moscow Team Olympiad) C. Division (数学)

最新文章

热门文章