知识点 - 因数之和因数个数公式

解决问题类型：

问有几个因数，因数之和，

或者问某些特定约数之和，比如不能被大于4的平方数整除的约数之和（即质因数的次数都为1）

结论

若对 $n$ 质因数分解得到 $p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$ 则有

因数个数公式：

$(e_1 + 1) \cdot (e_2 + 1) \cdots (e_k + 1)$

e.g.：设 $p_1^{e_1} \cdot 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}$
显然 $d(n)=(e_1 + 1) \cdot (e_2 + 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}$

e.g.设 $p_1^{e_1} \cdot p_2^{e_2}$
$\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}$

$d (n)$ and $\sigma(n)$ 都是积性函数

可以迪利克雷卷积

质因数的次数都为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)$

复杂度：

公式题，复杂度在乘法和快速幂上，

$O (k * l o g e)$

也可以对 $\left(1 + p_1 + p_1^2 + \dots + p_1^{e_1}\right)$ 如果二分递归求：举例来说， $1+a+a^2+a^3+a^4=(1+a)*(1+a^2)+a^2;(1+a)=1*(1+a)$ 。根据奇偶二分下去。直到只有一个数为止。

$O(k*log^2 e)$

例题

Sumdiv

Let S be the sum of all natural divisors of A^B. Determine S modulo 9901.

代码

#include<cstdio> #include<cstring> #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 <cstdio> #include <cmath> #include <iostream> #include <algorithm> 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<<endl;continue;} 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<<endl; } return 0; }

今天的文章知识点 - 因数之和因数个数公式分享到此就结束了，感谢您的阅读。

知识点 - 因数之和 因数个数公式