poj_1845_Sumdiv

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).

这道题目令我很不解的就是在等比求和的时候。大佬们分奇偶项数用二分递归求。而我的思路是乘法逆元*P₁(P₁^n -1)，也就是等比数列求和，在我出的数据中所得结果相同（rand随机出数)。。。不知道是什么原理

一开始想到的是A%mod^B，一举大数据直接炸。很快就想到唯一分解定理，然后等比求和，再然后就晾在等比求和上了。

AC代码：

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include "cstdio"

using namespace std;

#define ll long long

#define mod 9901

#define N 1000010

ll prime[N];

bool vis[N];

ll p[N];

ll pn=0;

ll POW(ll a,ll n)

{

    ll base=a,ret=1;

    while(n)

    {

        if(n&1) ret=(ret%mod*base)%mod;

        base=(base*base)%mod;

        n>>=1;

    }

    return ret%mod;

}

__int64 sum(__int64 p,__int64 n)  //递归二分求 (1 + p + p^2 + p^3 +...+ p^n)%mod

{                          //奇数二分式 (1 + p + p^2 +...+ p^(n/2)) * (1 + p^(n/2+1))

    if(n==0)               //偶数二分式 (1 + p + p^2 +...+ p^(n/2-1)) * (1+p^(n/2+1)) + p^(n/2)

        return 1;

    if(n%2)  //n为奇数,

        return (sum(p,n/2)*(1+POW(p,n/2+1)))%mod;

    else     //n为偶数

        return (sum(p,n/2-1)*(1+POW(p,n/2+1))+POW(p,n/2))%mod;

}

int main()

{

    for (int i = 2; i < N; i++) {

        if (vis[i]) continue;

        prime[pn++] = i;

        for (int j = i; j < N; j += i)

            vis[j] = 1;

    }

    ll a,b;

    while(~scanf("%lld%lld",&a,&b))

    {

        memset(p,0,sizeof(p));

        ll ans=1;

        for(int i=0;prime[i]*prime[i]<=a;i++)

        {

            ll tem=0;

            while(a%prime[i]==0)

            {

                tem++;

                a/=prime[i];

            }

            if(tem)

            {

                p[prime[i]]=tem;

            }

        }

        if(a!=1)

        {

                ll rev=POW(a-1,9899);

                ll res=sum(a,b);

                ans=ans*res%mod;

        }

        for(int i=0;i<pn;i++)

        {

            if(p[prime[i]])

            {

                ll rev=POW(prime[i]-1,9899);

                ll res=sum(prime[i],p[prime[i]]*b);

                ans=ans*res%mod;

            }

        }

        cout<<ans<<endl;

    }

}

巴特西

poj_1845_Sumdiv

最新文章

热门文章