2025年唯一分解定理

科技前沿 • 2025-02-22 14:57 • 阅读 65

大家好，我是讯享网，很高兴认识大家。

什么是唯一分解定理？

唯一分解定理的应用

1.求数n的因子个数：（1+a1）·(1+a2)·(1+a3)·(1+a4)…·(1+an)
a1,a2,这些分别是素数因子的幂次数
因为当我的a1=3时那我n的因子肯定会有 p1^0 p1 ^1 p1 ^2 p1 ^3 这四个数

然后再和p2的个数搭配起来就是两个数的因子数相乘了 p1^x 可以与 p2 ^y 随意搭配，所以进行乘法

2.求所有因子之和：(q1^0+q1 ^ 1+q1 ^2…q1 ^a1）·（q2 ^0+q2 ^1+q2 ^2…q2 ^ a2）·…·（qn ^0+qn ^n+qn ^2…qn ^an），与上原理相同，不过是求所有因子之和。
3. 用唯一分解求a,b的gcd,lcm（ak,bk为质数的幂）:
a,b是n的两个因子
a=p1^a1×p2 ^a2…pk ^ak;
b=p1^b1×p2 ^b2…pk ^bk;
n=p1^e1×p2 ^e2…pk ^ek;
gcd(a,b)=p1^min(a1,b1)·p2 ^ min(a2,b2)·…pk ^min(ak,bk)
lcm(a,b)=p1^max(a1,b1)·p2 ^max(a2,b2)·…pk ^max(ak,bk)
针对3的例题：

Pairs Forming LCM LightOJ - 1236

Find the result of the following code:

long long pairsFormLCM( int n ) { 
    long long res = 0; for( int i = 1; i <= n; i++ ) for( int j = i; j <= n; j++ ) if( lcm(i, j) == n ) res++; // lcm means least common multiple return res; }

讯享网

A straight forward implementation of the code may time out. If you analyze the code, you will find that the code actually counts the number of pairs (i, j) for which lcm(i, j) = n and (i ≤ j).
Input
Input starts with an integer T (≤ 200), denoting the number of test cases.

讯享网

Each case starts with a line containing an integer n (1 ≤ n ≤ 1014).

Sample Input

讯享网15 2 3 4 6 8 10 12 15 18 20 21 24 25 27 29

Sample Output

Case 1: 2 Case 2: 2 Case 3: 3 Case 4: 5 Case 5: 4 Case 6: 5 Case 7: 8 Case 8: 5 Case 9: 8 Case 10: 8 Case 11: 5 Case 12: 11 Case 13: 3 Case 14: 4 Case 15: 2

题解：先对n进行素因子分解，由于ei=max(ai,bi).所以，当ai=ei时，bi可以取[0,ei]之间任何一个数，当bi=ki时，ai可以取[0,ei]之间任何一个数，但是ai=bi=ei这种情况会有重复，所以情况数就是2×(ei+1)-1;又由于a<=b，只有当a=b=n时，a,b的最小公倍数才会是n,所以总的情况数
sum=0;
for(i=1 range k) sum+= 2*ei+1;
///
sum=sum/2+1;(最后加一就是因为当两个数相等时只有（n,n)这种情况）
cout<<sum<<endl;
代码：

讯享网#include <bits/stdc++.h> using namespace std; const int maxx=1e7+5; bool vis[maxx]; int prime[]; int cnt=0; void is_prime() { 
    memset(vis,false,sizeof(vis));//全部初始化为素数 vis[1]=true; for(int i=2; i<maxx; i++) { 
    if(!vis[i]) prime[cnt++]=i; for(int j=0; j<cnt&&i*prime[j]<maxx; j++) { 
    vis[i*prime[j]]=1; if(i%prime[j]==0) break; } } } int main() { 
    is_prime(); int t; cin>>t; int Case=1; while(t--) { 
    long long int n; scanf("%lld",&n); int ans=1; for(int i=0;i<cnt&&prime[i]*prime[i]<=n;i++) { 
    if(n%prime[i]==0) { 
    int x=0; while(n%prime[i]==0) { 
    n=n/prime[i]; x++; } ans*=(2*x+1); } } if(n>1) { 
    ans*=(2*1+1); } printf("Case %d: %d\n",Case++,ans/2+1); } return 0; }

学习该博客：https://www.cnblogs.com/Lis-/p/9692677.html

2025年唯一分解定理

什么是唯一分解定理？

唯一分解定理的应用

Pairs Forming LCM LightOJ - 1236

相关推荐