　　题目传送门

Sumdiv

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 26041		Accepted: 6430

Description

Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901).

Input

The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.

Output

The only line of the output will contain S modulo 9901.

Sample Input

2 3

Sample Output

Hint

2^3 = 8.
The natural divisors of 8 are: 1,2,4,8. Their sum is 15.
15 modulo 9901 is 15 (that should be output).

Source

Romania OI 2002

　　分析：

　　题意就是求A^B在mod 9901下的约数和。

　　之前遇到过一个一模一样的题，直接分解质因数，把每一个质因数按照费马小定理对9901-1取模然后直接暴力计算就过了，但是在这里死活过不了。然后稍微推了一下发现这么做有BUG，因为9900不是质数，取模的时候会出错。

　　然后翻了一下lyd的书，正解思路了解一下。

　　同样先分解质因数，再由约数和定理ans=(1+q1+q1^2+...+q1^(c1*b))*(1+q2+q2^2+...+q2^(c2*b))*...*(1+qn+qn^2+...qn^(cn*b))可得，对于每一个质因数qi，求(1+qi+qi^2+...+qi^(ci*b))时，可以用等比数列的求和公式求，即(qi^(b*ci+1))/(qi-1)，但是除法并不满足取模的分配律，所以就用逆元来代替。也就是求1/(qi-1)在模9901下的逆元。但是要注意，qi-1可能被9901整除，此时不存在逆元。不过可以发现，此时qi mod 9901=1，那么(1+qi+qi^2+...+qi^(b*ci))=1+1+1+...+1（b*ci+1个1），特判即可。

　　Code：

//It is made by HolseLee on 21st June 2018

//POJ 1845

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<iostream>

#include<iomanip>

#include<algorithm>

using namespace std;

typedef long long ll;

const ll mod=;

const ll N=5e6+;

ll A,B,q[N],f[N],ans,tot,cnt;

void fenjie()

{

    for(ll i=;i*i<=A;i++){

        if(A%i==){

            q[++cnt]=i;

            while(A%i==){

            f[cnt]++;A/=i;}

        }

    }

    if(A>)q[++cnt]=A,f[cnt]++;

}

inline ll power(ll x,ll y)

{

    ll ret=;

    while(y>){

        if(y&)ret=(ret*x)%mod;

        x=(x*x)%mod;y>>=;}

    return ret;

}

void work()

{

    fenjie();ans=;

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

        if((q[i]-)%mod==){

            ans=(ans*(B*f[i]+)%mod)%mod;

            continue;}

        ll x=power(q[i],B*f[i]+);

        x=(x-+mod)%mod;

        ll y=power(q[i]-,mod-);

        ans=(ans*x*y)%mod;

    }

    printf("%lld",ans);

}

int main()

{

    cin>>A>>B;

    work();return ;

}

巴特西

POJ1845 Sumdiv [数论，逆元]

Sumdiv

最新文章

热门文章