【数论系列】 唯一分解定理

大家好，欢迎来到IT知识分享网。

目录

一. 定理内容

二. 实现代码

1. 素数打表分解

2. 直接分解法

三. 定理性质

1. 求某数约数的个数

2. 求某数所有约数的和

四. 定理应用

1. 欧拉函数求互质

2. 化大数运算为小数运算

一. 定理内容

任何一个大于1的自然数 N，如果N不为质数，那么N可以唯一分解成有限个质数的乘积N=P1^a1*P2^a2*P3^a3*……*Pn^an，这里P1<P2<P3……<Pn均为质数，其中指数ai是正整数。这样的分解称为 N 的标准分解式。

        唯一分解定理又称为算术基本定理，其性质是每个大于1的自然数N（非质数）均可以被分解且他们的分解形式是唯一的。注意：

（1）判断数字n的因子有哪些，只需要枚举到sqrt(n)即可；

（2）判断n范围内哪些数字能够成为因子，只需枚举到n/2即可；

二. 实现代码

1. 素数打表分解

（1）基本模板

        遍历所有素数，若有素数因子，则除尽该因子后继续遍历，直到该数字变为1。

#include <iostream> #include<bits/stdc++.h> using namespace std; const int maxn = 10000 + 7; int prime[maxn],len,n,num; int p[maxn],q[maxn]; bool judge[maxn]; void isPrime(){//素数打表 len = 0; memset(judge,0,sizeof(judge)); judge[1] = 1; for(int i = 2;i<=maxn;i++){ if(!judge[i])prime[len++] = i; for(int j = 0;j<len;j++){ if(i*prime[j]>maxn)break; judge[i*prime[j]] = 1; if(i%prime[j]==0)break; } } } void Split(int k){//分解 memset(p,0,sizeof(p)); memset(q,0,sizeof(q)); for(int i = 0;i<len;i++){ while(k%prime[i]==0){ if(!p[num])p[num] = prime[i]; q[num]++; k/=prime[i]; } if(p[num])num++; if(k==1)break;//退出条件是变为1 } } int main() { isPrime(); while(scanf("%d",&n)!=EOF){ num = 0; Split(n); printf("%d = ",n); for(int i = 0;i<num;i++){ if(i!=0)printf("*"); printf("%d^%d",p[i],q[i]); } printf("\n"); } return 0; } 

（2）优化模板

        根据求因子条件，素数只枚举到prime[i]*prime[i]<=n ， 最后若n>1就说明还剩下一个一次方的素数。

        原因是：若n%prime[i]==0，则n = prime[i] * q，然后我们把n里面的prime[i]因子除尽以后，n = 1*k，n就变成了一个新的数字，因为我们的素数枚举是从小到大的，小的除尽了，如果k是一个合数，那么肯定能拆成素数乘积，而且这个素数是肯定>prime[i]的，也一定满足prime[j]*prime[j] <=n是能继续拆的；另一方面，如果只剩下一个素数，就不会满足prime[j]*prime[j]<=n了，所以这种方法是可行的。

void Split(int k){ memset(p,0,sizeof(p)); memset(q,0,sizeof(q)); for(int i = 0;i<len&&prime[i]*prime[i]<=k;i++){//判断条件变化 while(k%prime[i]==0){ if(!p[num])p[num] = prime[i]; q[num]++; k/=prime[i]; } if(p[num])num++; } if(k>1){p[num] = k;q[num++]++;}//结尾判断 }

2. 直接分解法

void Split(int k){ memset(p,0,sizeof(p)); memset(q,0,sizeof(q)); for(int i = 2;i*i<=k;i++){ while(k%i==0){ if(!p[num])p[num] = i; q[num]++; k/=i; } if(p[num])num++; } if(k>1){p[num] = k;q[num++]++;} }

三. 定理性质

1. 求某数约数的个数

已知：N = (p1^n1) * (p2^n2) * (p3^n3)  *…..* (pk^nk)

则：N的所有约数个数NumCnt = (1+n1)*(1+n2)*(1+n3)*…..*(1+nk)

2. 求某数所有约数的和

已知：N = (p1^n1) * (p2^n2) * (p3^n3)  *…..* (pk^nk)

则：N的所有约数的和 NumSum = (1 + p1 + p1^2 + p1^3 + … + p1^n1) * (1 + p2 + p2^2 + …..) * …… * (1 + pk + pk^2 + …)；

即：各因子在幂次上的等比数列之积

#include <iostream> #include<bits/stdc++.h> using namespace std; const int maxn =  + 7; typedef long long LL; LL prime[maxn],tot; bool isPrime[maxn]; void init(){ tot = 0; memset(isPrime,0,sizeof(isPrime)); isPrime[1] = 1; for(int i = 2;i<maxn;i++){ if(!isPrime[i])prime[tot++] = i; for(int j = 0;j<tot;j++){ if(i*prime[j]>=maxn)break; isPrime[i*prime[j]] = 1; if(i%prime[j]==0)break; } } } int main() { init(); int T; scanf("%d",&T); while(T--){ LL a; scanf("%lld",&a); LL temp = a; LL NumCnt = 1; LL NumSum = 1; for(int i = 0;i<tot&&prime[i]*prime[i]<=temp;i++){ if(temp%prime[i]==0){ LL cnt = 0; while(temp%prime[i]==0){ cnt++; temp/=prime[i]; } NumCnt*=(1+cnt);//sum = (1+fac1)*(1+fac2)*..... NumSum*=(1-(LL)(pow(prime[i],cnt+1)+0.5))/(1-prime[i]); } } if(temp > 1){NumCnt*=2;NumSum*=(1+temp);} printf("%lld %lld\n",NumCnt,NumSum); } return 0; } 

四. 定理应用

1. 欧拉函数求互质

【数论系列】 唯一分解定理

2. 化大数运算为小数运算

Problem Description

 UVA – 10375

        组合数运算，优先考虑取模，但是此处直接运算没有取模，而且数量很大，因为保证输出结果不超过10^8，所以可以看出，结果不大但是中间运算过程中的乘阶会很大。

方法一：因为组合数分子与分母数量一致，我们直接乘一个，除一个。

方法二：利用唯一分解定理，把所有的数，拆分为小的素数，然后统一计算所有素数的乘积。

#include <iostream> #include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 10000 + 7; int prime[maxn],er[maxn],len; int p,q,r,s; bool judge[maxn]; void isPrime(){//筛素数 memset(judge,0,sizeof(judge)); judge[1] = 1; len = 0; for(int i = 2;i<maxn;i++){ if(!judge[i])prime[len++] = i; for(int j = 0;j<len;j++){ if(i*prime[j]>=maxn)break; judge[i*prime[j]] = 1; if(i%prime[j]==0)break; } } } void addPrime(int n,int d){ int ans = n; for(int i = 0;i<len;i++){//分解 while(ans%prime[i]==0){ er[i]+=d;//er保留所有素数的指数 ans/=prime[i]; } if(ans==1)break; } } void addMultiply(int n,int d){//(N!)^d for(int i = 2;i<=n;i++){ addPrime(i,d); } } int main() { isPrime(); while(scanf("%d%d%d%d",&p,&q,&r,&s)!=EOF){ memset(er,0,sizeof(er)); addMultiply(p,1); addMultiply(q,-1); addMultiply(p-q,-1); addMultiply(r,-1); addMultiply(s,1); addMultiply(r-s,1); double num = 1; for(int i = 0;i<len;i++){ num*=pow(prime[i],er[i]); } printf("%.5lf\n",num); } return 0; }