算术基本定理及其应用

女爷i 2022-05-18 00:09 547阅读 0赞

算术基本定理，又称为正整数的唯一分解定理，即：每个大于1的自然数均可写为质数的积，而且这些素因子按大小排列之后，写法仅有一种方式。例如: 6936=23×3×172，1200=24×3×52  6936 = 2 3 × 3 × 17 2 ， 1200 = 2 4 × 3 × 5 2 。

算术基本定理的内容由两部分构成：  
1. 分解的存在性：  
2. 分解的唯一性，即若不考虑排列的顺序，正整数分解为素数乘积的方式是唯一的。

N=pa11∗pa22∗pa33⋯∗pann=∏i=1npaii  N = p 1 a 1 ∗ p 2 a 2 ∗ p 3 a 3 ⋯ ∗ p n a n = ∏ i = 1 n p i a i

这里  p1<p2<p3<⋯<pn  p 1 < p 2 < p 3 < ⋯ < p n  且均为质数，其中指数  ai  a i  是正整数

--------------------

# 定理应用 #

--------------------

# N的正因数个数 #

一个大于1的正整数N，如果它的标准分解式为N=pa11pa22pa33⋯pann  N = p 1 a 1 p 2 a 2 p 3 a 3 ⋯ p n a n   
那么N的正因数个数为

σ0(N)=(1\+a1)(1\+a2)⋯(1\+an)  σ 0 ( N ) = ( 1 + a 1 ) ( 1 + a 2 ) ⋯ ( 1 + a n )

所以N的正因子个数为：  所 以 N 的 正 因 子 个 数 为 ：

σ(N)=∏i=1n(1\+ai)  σ ( N ) = ∏ i = 1 n ( 1 + a i )

--------------------

# N的全体正因数之和为 #

σ(N)=(1\+p1\+p21\+⋯\+pa11)(1\+p2\+p22\+⋯\+pa22)⋯(1\+pn\+p2n\+⋯\+pann)  σ ( N ) = ( 1 + p 1 + p 1 2 + ⋯ + p 1 a 1 ) ( 1 + p 2 + p 2 2 + ⋯ + p 2 a 2 ) ⋯ ( 1 + p n + p n 2 + ⋯ + p n a n )

σ(N)=(pa1\+11−1p1−1)(pa2\+12−1p2−1)(pa3\+13−1p3−1)⋯(pan\+1n−1pn−1)  σ ( N ) = ( p 1 a 1 + 1 − 1 p 1 − 1 ) ( p 2 a 2 + 1 − 1 p 2 − 1 ) ( p 3 a 3 + 1 − 1 p 3 − 1 ) ⋯ ( p n a n + 1 − 1 p n − 1 )

σ(N)=∏ni=1pai\+1i−1pi−1  σ ( N ) = ∏ i = 1 n p i a i + 1 − 1 p i − 1

所以N的全体正因子之和为：  所 以 N 的 全 体 正 因 子 之 和 为 ：

σ(N)=∏i=1npai\+1i−1pi−1  σ ( N ) = ∏ i = 1 n p i a i + 1 − 1 p i − 1

举个例子：  
12=22∗31=pa11∗pa22(p1=2a1=2p2=3a2=1)  12 = 2 2 ∗ 3 1 = p 1 a 1 ∗ p 2 a 2 ( p 1 = 2 a 1 = 2 p 2 = 3 a 2 = 1 )   
而12的因子有1,2,3,4,6,12  而 12 的 因 子 有 1 , 2 , 3 , 4 , 6 , 12

1=20∗30  1 = 2 0 ∗ 3 0   
2=21∗30  2 = 2 1 ∗ 3 0   
3=20∗31  3 = 2 0 ∗ 3 1   
4=22∗30  4 = 2 2 ∗ 3 0   
6=21∗31  6 = 2 1 ∗ 3 1   
12=22∗31  12 = 2 2 ∗ 3 1

左边加起来=1\+2\+3\+4\+6\+12=28=(20\+21\+22)∗(30\+31)=右边  左 边 加 起 来 = 1 + 2 + 3 + 4 + 6 + 12 = 28 = ( 2 0 + 2 1 + 2 2 ) ∗ ( 3 0 + 3 1 ) = 右 边

(20\+21\+22)  ( 2 0 + 2 1 + 2 2 )  是一个首项为1，公比为2的等比数列

(30\+31)  ( 3 0 + 3 1 )  是一个首项为1 ， 公比为3的等比数列

因为我们对n进行算数分解 所以不可能出现公比为1的情况

根据等比数列求和公式 (1−qn)/(1−q)  ( 1 − q n ) / ( 1 − q )

分子分母同时乘−1(qn−1)/(q−1)  − 1 ( q n − 1 ) / ( q − 1 )

因为第一项是从0  0 开始的 所以 对于paii p ia i 它的前n项和为(pai\+1i−1)/(pi−1)  ( p i a i + 1 − 1 ) / ( p i − 1 )   
所  
σ(N)=∏ni=1pai\+1i−1pi−1  σ ( N ) = ∏ i = 1 n p i a i + 1 − 1 p i − 1

--------------------

# 求1到n的因子和的和 #

公式：

ans=σ(1)\+σ(2)\+σ(3)\+⋯\+σ(n)  a n s = σ ( 1 ) + σ ( 2 ) + σ ( 3 ) + ⋯ + σ ( n )

这里以n=12  n = 12 为例：  
1:1  1 : 1   
2:1,2  2 : 1 , 2   
3:1,3  3 : 1 , 3   
4:1,2,4  4 : 1 , 2 , 4   
5:1,5  5 : 1 , 5   
6:1,2,3,6  6 : 1 , 2 , 3 , 6   
7:1,7  7 : 1 , 7   
8:1,2,4,8  8 : 1 , 2 , 4 , 8   
9:1,3,9  9 : 1 , 3 , 9   
10:1,2,5,10  10 : 1 , 2 , 5 , 10   
11:1,11  11 : 1 , 11   
12:1,2,3,4,6,12  12 : 1 , 2 , 3 , 4 , 6 , 12   
则  
ans=σ(1)\+σ(2)\+σ(3)\+⋯\+σ(12)  a n s = σ ( 1 ) + σ ( 2 ) + σ ( 3 ) + ⋯ + σ ( 12 )

ans=12∗1\+6∗2\+4∗3\+3∗4\+2∗5\+2∗6\+1∗7\+1∗8\+1∗9\+1∗10\+1∗11\+1∗12  a n s = 12 ∗ 1 + 6 ∗ 2 + 4 ∗ 3 + 3 ∗ 4 + 2 ∗ 5 + 2 ∗ 6 + 1 ∗ 7 + 1 ∗ 8 + 1 ∗ 9 + 1 ∗ 10 + 1 ∗ 11 + 1 ∗ 12

ans=∑ni=1n/i∗i  a n s = ∑ i = 1 n n / i ∗ i (这里n/i  n / i 是整除的意思)

然后我们这样看  
ans=12∗1\+6∗2\+4∗3\+3∗4\+2∗(5\+6)\+1∗(7\+8\+9\+10\+11\+12)  a n s = 12 ∗ 1 + 6 ∗ 2 + 4 ∗ 3 + 3 ∗ 4 + 2 ∗ ( 5 + 6 ) + 1 ∗ ( 7 + 8 + 9 + 10 + 11 + 12 )

则对于每一个 n/i  n / i  都有一个范围

n/i  n / i  范围\[l,r\]  \[ l , r \]   
当前n/i  n / i  在范围内 对ans  a n s 的贡献是  
12\[1,1\]12∗1  12 \[ 1 , 1 \] 12 ∗ 1   
6\[2,2\]6∗2  6 \[ 2 , 2 \] 6 ∗ 2   
4\[3,3\]4∗3  4 \[ 3 , 3 \] 4 ∗ 3   
3\[4,4\]3∗4  3 \[ 4 , 4 \] 3 ∗ 4   
2\[5,6\]2∗(5\+6)  2 \[ 5 , 6 \] 2 ∗ ( 5 + 6 )   
1\[7,12\]1∗(7\+8\+−−−\+12)  1 \[ 7 , 12 \] 1 ∗ ( 7 + 8 + − − − + 12 )  然后这里可以等差数列求和

可以发现 每一个l  l 等于上一个r\+1  r + 1  而r=n/(n/l)  r = n / ( n / l ) 这里是整除

/*
     *      求1到n的因子和的和
     *
     * 
     */
    
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    ll Sigma(ll n)
    {
        ll ans=0;
        ll r;
        for(ll l=1;l<=n;l=r+1)
        { 
            r=n/(n/l);
            ans+=(l+r)*(r-l+1)/2*(n/l);
    
            //(l+r)             首项+尾项
            //(r-l+1)           项数 
            //(l+r)*(r-l+1)/2   区间和
            //(n/l) 是拥有这样因子的区间个数 
            //      printf("l:%2lld  r:%2lld  l+r:%2lld  r-l+1:%lld     n/l:%2lld    ans:%3lld\n",l,r,l+r,r-l+1,n/l,ans); 
        }
        return ans;
    }
    
    int main()
    {
        ll n;
        while(~scanf("%lld",&n))
            printf("%lld\n",Sigma(n));
        return 0;
    }

--------------------

# 求1到n的因子个数的和 #

还是以n=12  n = 12 为例

ans=τ(1)\+τ(2)\+τ(3)\+τ(4)\+τ(5)\+τ(6)\+τ(7)\+τ(8)\+τ(9)\+τ(10)\+τ(11)\+τ(12)  a n s = τ ( 1 ) + τ ( 2 ) + τ ( 3 ) + τ ( 4 ) + τ ( 5 ) + τ ( 6 ) + τ ( 7 ) + τ ( 8 ) + τ ( 9 ) + τ ( 10 ) + τ ( 11 ) + τ ( 12 )   
ans=1\+2\+2\+3\+2\+4\+2\+4\+3\+4\+2\+6  a n s = 1 + 2 + 2 + 3 + 2 + 4 + 2 + 4 + 3 + 4 + 2 + 6   
ans=1∗1\+2∗5\+3∗2\+4∗3\+6∗1  a n s = 1 ∗ 1 + 2 ∗ 5 + 3 ∗ 2 + 4 ∗ 3 + 6 ∗ 1   
ans=∑ni=1(ni)  a n s = ∑ i = 1 n ( n i )

/*
     *  求1到n的因子个数的和
     *
     */
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    ll f(ll n)
    {
        ll ans=0;
        ll r;
        for(ll l=1;l<=n;l=r+1)
        {
            r=n/(n/l);
            ans+=n/l*(r-l+1);
            //(n/l)     代表因子个数 
            //(r-l+1)   是有这个因子个数的区间长度
        }
        return ans;
    }
    
    int main()
    {
        ll n;
        while(~scanf("%lld",&n))
            printf("%lld\n",f(n));
        return 0;
    }

--------------------

# GCD和LCM #

利用算术基本定理可以重新定义整数a和b的最大公因子gcd(a,b)  g c d ( a , b )  和最小公倍数lcm(a,b)  l c m ( a , b )   
将a和b写成

a=pa11pa22pa33⋯pann  a = p 1 a 1 p 2 a 2 p 3 a 3 ⋯ p n a n

b=pb11pb22pb33⋯pbnn  b = p 1 b 1 p 2 b 2 p 3 b 3 ⋯ p n b n

所以a和b的最大公因数与最小公倍数可以写成这个形式，也可以由下边这个形式求得  所 以 a 和 b 的 最 大 公 因 数 与 最 小 公 倍 数 可 以 写 成 这 个 形 式 ， 也 可 以 由 下 边 这 个 形 式 求 得

gcd(a,b)=pmin(a1,b1)1pmin(a2,b2)2pmin(a3,b3)3⋯pmin(an,bn)n  g c d ( a , b ) = p 1 m i n ( a 1 , b 1 ) p 2 m i n ( a 2 , b 2 ) p 3 m i n ( a 3 , b 3 ) ⋯ p n m i n ( a n , b n )

lcm(a,b)=pmax(a1,b1)1pmax(a2,b2)2pmax(a3,b3)3⋯pmax(an,bn)n  l c m ( a , b ) = p 1 m a x ( a 1 , b 1 ) p 2 m a x ( a 2 , b 2 ) p 3 m a x ( a 3 , b 3 ) ⋯ p n m a x ( a n , b n )

--------------------

未完待续…