洛谷 P1593 因子和题解

题面

这道题在数学方面没什么难度：

对于每一个正整数n：

质因数分解后可以写成n=a1^k1a2^k2……*ai^ki

所求的数的因数和f(n)就等于f(n)=(1+a1+a1^2+……+a1^k1)(1+a2+a2^2+……+a2^k2)……*(1+ai+ai^2+……+ai^ki)

利用等比数列通项公式可以O(1)的时间算出每一项；

然后可以使用扩展欧几里得，费马小定理或求解逆元。

但，仅仅是这样吗？

注意，模数p是9901，十分的小，但是要求逆元的数完全可能是9901的倍数，从而与9901不互质，从而没有逆元

例如：950497 1 ans=2；

在处理完以上的特殊情况后我们可以十分生气的一边骂出题人一边AC掉它；

#include <bits/stdc++.h>

#define int long long

#define p 9901

using namespace std;

long long KSM(long long a,long long b)

{

    long long res=;

    while(b){

        if(b&) res=res*a%p;

        a=a*a%p;

        b/=;

    }

    return res;

}

long long yinzi[],cnt,num[];

void fenjie(int a)

{

    for(int i=;i<=sqrt(a);i++){

        if(a%i==){

            yinzi[++cnt]=i;

            while(a%i==){

                ++num[cnt];

                a/=i;

            }

        }

    }

    if(a>=){

        yinzi[++cnt]=a;

        num[cnt]=;

    }

}

signed main()

{

    int a,b;

    cin>>a>>b;

    fenjie(a);

    for(int i=;i<=cnt;i++){

        num[i]=num[i]*b;

    }

    long long ans=;

    for(int i=;i<=cnt;i++){

        ans=(ans*(-KSM(yinzi[i],num[i]+))%p*KSM((-yinzi[i]),p-))%p;

    }

    if(ans==){

        cout<<""<<endl;

        return ;

    }

    cout<<ans;

}

巴特西

洛谷 P1593 因子和题解

最新文章

热门文章

巴特西

洛谷 P1593 因子和 题解

最新文章

热门文章

洛谷 P1593 因子和题解