POJ 1845-Sumdiv 題解（數論，約數和公式，逆元，高中數學）

題目描述

給定A,B，求A^B的所有因數的和，再MOD 9901

輸入

一行兩個整數 A 和 B。

輸出

一行，一個整數

樣例輸入

2 3

樣例輸出

15

提示

對於100%的數據滿足：0 <= A,B <= 50000000

這道題首先要想到有一個因數和公式

f[a] = ( 1 + p1 + p1^2 + .... + p1^q1 ) * ( 1 + p2 + p2^2 + .... + p2^q2 ) * ...... * ( 1 + pn + pn^2 +.....+ pn^qn )

由此我們知道，這道題需要分解質因數（唯一分解定理？？？

A^B可以直接分A，每個分出數的指數再×B就行（這應該都會

所以我們可以先打個素數表..

因為a，b都在50000000，計算器一算7000多的表就夠了..

我們再觀察因數和公式，如果一個一個求救太麻煩了，我們就發現了這是等比數列啊！！！

等比數列公式相信大家都會...

因為除數可能為負數，所以式子要上下都×-1整理一下

但這又有可能出現不是整數的情況，我們就需要用乘法逆元了（當時我卡在這了

這裡先貼一個寫的挺好的乘法逆元

inline long long extend_gcd(long long a,long long b,long long &x,long long &y)
{
    if(a==0&&b==0)
        return -1ll;
    if(b==0)
    {
        x=1ll;
        y=0ll;
        return a;
    }
    long long d=extend_gcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
inline long long mod_reverse(long long a,long long n)
{
    long long x,y,d=extend_gcd(a,n,x,y);
    if(d==1)
        return (x%n+n)%n;
    else
        return -1ll;
}

快速冪和乘法取模就不說了

下麵貼代碼

#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<cmath> 
#define ll long long 
ll vis[8000]={0}; 
ll ys[8000]={0},zs[8000]={0}; 
ll vis1[8000]={0}; 
ll ac[8000]={0}; 
using namespace std; 
ll n; 
ll qmod(ll i,ll j)  
{  
    ll ans=1;  
    while(j)  
    {  
        if(j&1)  
        {  
            ans*=i;  
            ans%=9901;  
        }  
        i=i*i%9901;  
        j>>=1;  
    }  
    return ans%9901;  
}  
void prime() 
{ 
    ll i,j,k=0; 
    for(i=2;i<=7100;i++) 
    { 
        vis[i]=i; 
    } 
    i=2; 
    while(i*i<=7100) 
    { 
        if(vis[i]!=0) 
        { 
            j=i<<1; 
            while(j<=7100) 
            { 
                if(vis[j]!=0) 
                { 
                    k++; 
                } 
                vis[j]=0; 
                j=j+i; 
            } 
        } 
        i++; 
    }    
} 
int main() 
{ 
    ll k=1; 
    ll i,j; 
    ll A,b; 
    ll a,n; 
    cin>>a>>b; 
    A=a; 
    n=sqrt(a); 
    prime(); 
    for(i=2;i<=n;i++) 
    { 
        while((vis[i]!=0)&&(a%vis[i]==0)) 
        { 
            vis1[i]=1; 
            ys[k]=vis[i]%9901; 
            zs[k]++; 
            a=a/vis[i]; 
        } 
        if(vis1[i]==1) 
        { 
            k++; 
        } 
    } 
    k--; 
    ll step=0; 
    ll re=0,cf=0; 
    if(a!=1&&a!=A) 
    { 
        ys[k+1]=a%9901; 
        zs[k+1]=1; 
        step=1; 
    } 
    else
    if(a==A) 
    { 
        ys[1]=a%9901; 
        zs[1]=1; 
        k=1; 
    } 
    if(step==1) 
    { 
        k++; 
    } 
    ll count=0; 
    for(i=1;i<=k;i++) 
    { 
        if(zs[i]!=0) 
        { 
            zs[i]=zs[i]*b; 
            count++; 
        } 
    } 
    for(i=1;i<=count;i++) 
    { 
        ll a1=qmod(ys[i]%9901,zs[i]+1); 
        a1=a1-1; 
        ll temp=(ys[i]-1)%9901; 
        ll a2=qmod(temp,9899); 
        ac[i]=((a1%9901)*(a2%9901))%9901; 
    } 
    ll sum=ac[1]; 
    for(i=2;i<=count;i++) 
    { 
        sum=((sum%9901)*(ac[i]%9901))%9901; 
    } 
    cout<<sum; 
}