求一个数的所有因子和可以用算术基本定理，下面是它的两个重要应用：
（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;i
1&&(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;i
1) ans=ans*get_sum(n,m)%MOD; printf("%lld\n",ans); } return 0; }
?
?
?
?