知识点 - 因数之和 因数个数公式
解决问题类型：
问有几个因数，因数之和，
或者问某些特定约数之和，比如不能被大于4的平方数整除的约数之和（即质因数的次数都为1）
结论
若对
n
n
n 质因数分解得到
p
1
e
1
⋅
p
2
e
2
⋯
p
k
e
k
p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}
p1e1⋅p2e2⋯pkek则有
因数个数公式：
d
(
n
)
=
(
e
1
+
1
)
⋅
(
e
2
+
1
)
⋯
(
e
k
+
1
)
d(n) = (e_1 + 1) \cdot (e_2 + 1) \cdots (e_k + 1)
d(n)=(e1+1)⋅(e2+1)⋯(ek+1)
e.g.：设
n
=
p
1
e
1
⋅
p
2
e
2
n = p_1^{e_1} \cdot p_2^{e_2}
n=p1e1⋅p2e2
1
p
2
p
2
2
…
p
2
e
2
1
1
p
2
p
2
2
…
p
2
e
2
p
1
p
1
p
1
⋅
p
2
p
1
⋅
p
2
2
…
p
1
⋅
p
2
e
2
p
1
2
p
1
2
p
1
2
⋅
p
2
p
1
2
⋅
p
2
2
…
p
1
2
⋅
p
2
e
2
⋮
⋮
⋮
⋮
⋱
⋮
p
1
e
1
p
1
e
1
p
1
e
1
⋅
p
2
p
1
e
1
⋅
p
2
2
…
p
1
e
1
⋅
p
2
e
2
\begin{array}{c|ccccc} & 1 & p_2 & p_2^2 & \dots & p_2^{e_2} \\\\ \hline 1 & 1 & p_2 & p_2^2 & \dots & p_2^{e_2} \\\\ p_1 & p_1 & p_1 \cdot p_2 & p_1 \cdot p_2^2 & \dots & p_1 \cdot p_2^{e_2} \\\\ p_1^2 & p_1^2 & p_1^2 \cdot p_2 & p_1^2 \cdot p_2^2 & \dots & p_1^2 \cdot p_2^{e_2} \\\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\\\ p_1^{e_1} & p_1^{e_1} & p_1^{e_1} \cdot p_2 & p_1^{e_1} \cdot p_2^2 & \dots & p_1^{e_1} \cdot p_2^{e_2} \\\\ \end{array}
1p1p12⋮p1e111p1p12⋮p1e1p2p2p1⋅p2p12⋅p2⋮p1e1⋅p2p22p22p1⋅p22p12⋅p22⋮p1e1⋅p22…………⋱…p2e2p2e2p1⋅p2e2p12⋅p2e2⋮p1e1⋅p2e2 显然
d
(
n
)
=
(
e
1
+
1
)
⋅
(
e
2
+
1
)
d(n)=(e_1 + 1) \cdot (e_2 + 1)
d(n)=(e1+1)⋅(e2+1)
因数和公式
σ
(
n
)
=
p
1
e
1
+
1
−
1
p
1
−
1
⋅
p
2
e
2
+
1
−
1
p
2
−
1
⋯
p
k
e
k
+
1
−
1
p
k
−
1
\sigma(n) = \frac{p_1^{e_1 + 1} - 1}{p_1 - 1} \cdot \frac{p_2^{e_2 + 1} - 1}{p_2 - 1} \cdots \frac{p_k^{e_k + 1} - 1}{p_k - 1}
σ(n)=p1−1p1e1+1−1⋅p2−1p2e2+1−1⋯pk−1pkek+1−1
e.g.设
n
=
p
1
e
1
⋅
p
2
e
2
n = p_1^{e_1} \cdot p_2^{e_2}
n=p1e1⋅p2e2
σ
(
n
)
=
(
1
+
p
1
+
p
1
2
+
⋯
+
p
1
e
1
)
⋅
(
1
+
p
2
+
p
2
2
+
⋯
+
p
2
e
2
)
∵
1
+
p
1
+
p
1
2
+
⋯
+
p
1
e
1
=
p
1
e
1
+
1
−
1
p
1
−
1
∴
σ
(
n
)
=
p
1
e
1
+
1
−
1
p
1
−
1
⋅
p
2
e
2
+
1
−
1
p
2
−
1
\sigma(n)=\left(1 + p_1 + p_1^2 + \dots + p_1^{e_1}\right) \cdot \left(1 + p_2 + p_2^2 + \dots + p_2^{e_2}\right)\\ \because 1 + p_1 + p_1^2 + \dots + p_1^{e_1} = \frac{p_1^{e_1 + 1} - 1}{p_1 - 1}\\ \therefore\sigma(n) = \frac{p_1^{e_1 + 1} - 1}{p_1 - 1} \cdot \frac{p_2^{e_2 + 1} - 1}{p_2 - 1}
σ(n)=(1+p1+p12+⋯+p1e1)⋅(1+p2+p22+⋯+p2e2)∵1+p1+p12+⋯+p1e1=p1−1p1e1+1−1∴σ(n)=p1−1p1e1+1−1⋅p2−1p2e2+1−1
d
(
n
)
d(n)
d(n) and
σ
(
n
)
\sigma(n)
σ(n)都是积性函数
可以迪利克雷卷积
质因数的次数都为1的因数和公式
1
+
p
1
+
p
2
+
⋯
+
p
k
+
p
1
⋅
p
2
+
p
1
⋅
p
3
+
⋯
+
p
k
−
1
⋅
p
k
+
p
1
⋅
p
2
⋅
p
3
+
⋯
+
p
1
⋅
p
2
⋯
p
k
−
1
⋅
p
k
=
(
p
1
+
1
)
⋅
(
p
1
+
1
)
⋯
(
p
k
+
1
)
1+p_1+p_2+\cdots+p_k+\\p_1\cdot p_2+p_1\cdot p_3+\cdots+ p_{k-1}\cdot p_k+\\p_1\cdot p_2\cdot p_3 +\cdots + p_1\cdot p_2\cdots p_{k-1}\cdot p_k\\ =(p_1+1)\cdot(p_1+1)\cdots(p_k+1)
1+p1+p2+⋯+pk+p1⋅p2+p1⋅p3+⋯+pk−1⋅pk+p1⋅p2⋅p3+⋯+p1⋅p2⋯pk−1⋅pk=(p1+1)⋅(p1+1)⋯(pk+1)
复杂度：
公式题，复杂度在乘法和快速幂上，
O
(
k
∗
l
o
g
e
)
O(k*log e)
O(k∗loge)
也可以对
(
1
+
p
1
+
p
1
2
+
⋯
+
p
1
e
1
)
\left(1 + p_1 + p_1^2 + \dots + p_1^{e_1}\right)
(1+p1+p12+⋯+p1e1)如果二分递归求：举例来说，
1
+
a
+
a
2
+
a
3
+
a
4
=
(
1
+
a
)
∗
(
1
+
a
2
)
+
a
2
;
(
1
+
a
)
=
1
∗
(
1
+
a
)
1+a+a^2+a^3+a^4=(1+a)*(1+a^2)+a^2;(1+a)=1*(1+a)
1+a+a2+a3+a4=(1+a)∗(1+a2)+a2;(1+a)=1∗(1+a)。根据奇偶二分下去。直到只有一个数为止。
O
(
k
∗
l
o
g
2
e
)
O(k*log^2 e)
O(k∗log2e)
例题
Sumdiv
Let S be the sum of all natural divisors of A^B. Determine S modulo 9901.
代码
#include
#include
#ifdef unix
#define LL "%lld"
#else
#define LL "%I64d"
#endif
#define mod 9901
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll tot,c[N/3],prime[N/3];
bool check[N]={1,1};
void get_prime(){
ll n=10010;
for(ll i=2;i<=n;i++){
if(!check[i]) prime[++tot]=i;
for(ll j=1;j<=tot&&i*prime[j]<=n;j++){
check[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
ll mul(ll a,ll p,ll M){
ll res=0;
for(;p;p>>=1,a=(a+a)%M) if(p&1) res=(res+a)%M;
return res;
}
ll fpow(ll a,ll p,ll M){
ll res=1;
for(;p;p>>=1,a=mul(a,a,M)) if(p&1) res=mul(res,a,M);
return res;
}
void factor(ll A,ll B){
ll ans=1;
for(ll i=1;prime[i]*prime[i]<=A;i++){
if(A%prime[i]==0){
ll num=0;
while(A%prime[i]==0) num++,A/=prime[i];
ll MOD=(prime[i]-1)*mod;
ans*=(fpow(prime[i],num*B+1,MOD)+MOD-1)/(prime[i]-1);
ans%=mod;
}
}
if(A>1){
ll MOD=mod*(A-1);
ans*=(fpow(A,B+1,MOD)+MOD-1)/(A-1);
ans%=mod;
}
printf(LL"\n",ans);
}
int main(){
get_prime();
for(ll A,B;scanf(LL LL,&A,&B)==2;) factor(A,B);
return 0;
}
//递归二分代码：
#include
#include
#include
#include
using namespace std;
const int mod=9901;
int pow_mod(int a,int b)
{
a=a%mod;
int s=1;
while(b)
{
if(b&1)
s=(s*a)%mod;
a=(a*a)%mod;
b=b>>1;
}
return s;
}
int sum(int a,int b)//求1+a+a^2+...+a^b
{
if(b==1)return 1;
if(b&1)return (sum(a,b/2)*(1+pow_mod(a,b/2+1))+pow_mod(a,b/2))%mod;
else return sum(a,b/2)*(1+pow_mod(a,b/2))%mod;
}
int main()
{
int a,b;
while(cin>>a>>b)
{
if(a<=1||b==0){cout<<1< int ans=1,i,j,k,t,n,m; n=(int)sqrt(a+0.5); for(i=2;i<=n;i++) { if(a%i==0) { t=0; while(a%i==0){ a=a/i; t++; } ans=ans*sum(i,t*b+1)%mod; } } if(a>1) ans=ans*sum(a,b+1)%mod; cout<<(ans+mod)%mod< } return 0; }