程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj 1845 Sumdiv (算術基本定理求一個數因子和)

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

編輯:關於C++
求一個數的所有因子和可以用算術基本定理,下面是它的兩個重要應用:
(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;
}

 

 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved