poj 1845 Sumdiv (算術基本定理求一個數因子和)

求一個數的所有因子和可以用算術基本定理，下面是它的兩個重要應用：
（1）一個大於1的正整數N，如果它的標准分解式為： N=(P1^a1)*(P2^a2)......(Pn^an)
那麼它的正因數個數為（1+a1)(1+a2).....(1+an)。
（2） 它的全體正因數之和為d(N)=(1+p1+...p1^an)(1+p2+...p2^a2)...(1+pn+...+pn^an)
和求一個數正因數個數的方法類似.
可以先打表出sqrt(n)以內的所有素數（當然也可以不打表）,因為n的素因數中最多只有一個大於sqrt(n)(以前題目中有證明過),
所以可以最後處理它。對於每一項都是一個等比數列，求和很容易。


下面以poj 1845 Sumdiv為例。
求n^m%p,p為素數9901.
1)因為n和m很大，所以可以處理出n的所有素因數,然後^m即每個因數指數*m。此題可以不用預處理所有素數，直接分解素因數,對於這道題時間復雜度可接受;
2)用到快速冪運算。

3）在求等比數列和取模的時候兩種方法：1. 用等比數列求和公式：S=a1*（q^n-1）/(q-1)， 要用到(q-1)模9901的逆元，可以用歐拉定理或擴展歐幾裡得來求，但因為 mod 為素數,所以a的逆元為a^(mod-2)%mod,用快速冪來求。 2.遞歸形式的二分

 

對於逆元補充：費馬小定理(Fermat Theory)是數論中的一個重要定理，其內容為： 假如p是質數，且Gcd(a,p)=1，那麼 a(p-1) ≡1（mod p） 即：假如a是整數，p是質數，且a,p互質(即兩者只有一個公約數1)，那麼a的(p-1)次方除以p的余數恆等於1。

 

//逆元法求解

 

#include
#include
#include
#include
#include
#define maxn 10000
#define ll long long
using namespace std;
const ll MOD=9901;
ll prime[maxn],num,flag[maxn+5];
ll pow_mod(ll a,ll b,ll p){ //快速冪
    ll ret=1;
    while(b){
        if(b&1) ret=(ret*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return ret;
}
void get_prime(){          //篩素數
    memset(flag,0,sizeof(flag));
    num=0;
    for(ll i=2;i1&&(n-1)%MOD==0) ans=ans*(pow_mod(n,m+1,MOD*(n-1))/(n-1))%MOD;   //如果(n-1)%mod==0,不能求逆元了
        else if(n>1) ans=ans*get_sum(n,m)%MOD;
        printf("%lld\n",ans);                //剛開始沒加mod wa了好幾遍，因為這種方法ans可能為負
    }
    return 0;
}

 

//二分法求解

#include
#include
#include
#include
#include
#define maxn 10000
#define ll long long
using namespace std;
const ll MOD=9901;
ll prime[maxn],num,flag[maxn+5];
ll pow_mod(ll a,ll b,ll p){ //快速冪
    ll ret=1;
    while(b){
        if(b&1) ret=(ret*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return ret;
}
void get_prime(){          //篩素數
    memset(flag,0,sizeof(flag));
    num=0;
    for(ll i=2;i1) ans=ans*get_sum(n,m)%MOD;
        printf("%lld\n",ans);
    }
    return 0;
}