首页 > > 程序设计 > C/C++ >

POJ 1845-Sumdiv 题解（数论，约数和公式，逆元…

2018-06-17 22:25:44来源：未知阅读 ()

题目描述

给定A,B，求A^B的所有因数的和，再MOD 9901

输入

一行两个整数 A 和 B。

输出

一行，一个整数

样例输入

2 3

样例输出

提示

对于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; 
}