数论-约数

作者: dachengquan | 来源:发表于2020-07-29 16:19 被阅读0次

1约数

定义：若整数n除以整数d的余数为0，即d能整除n，则称d是n的约数，n是d的倍数，记作 $d|n$ 。

1.2算数基本定理的推导

在算法基本定理中 $N=p_1^{c_1}p_2^{c_2}...p_m^{c_m}$ ,其中 $c_i$ 都是正整数， $p_i$ 都是质数，且满足 $p_1<p_2<...<p_m$ ,则N的正约数集合可以表示为：
${p_1^{b_1}p_2^{b_2}...p_m^{b_m}}，其中0\leq b_i\leq c_i$
N的正约数个数为
$(c_1+1)*(c_2+1)*...*(c_m+1)= \prod_{i=1}^m (c_i+1)$
N的所有正约数的和
$(1+p_1+p_1^2+...+p_2^{c_1})*...*(1+p_m+p_m^2+...+p_m^{c_m})=\prod_{i=1}^m(\sum_{j=0}^{c_i}(p_i)^j)$

1.3求N的正约数集合-试除法

若d> $\sqrt{n}$ 是一个约数那么n/d< $\sqrt{n}$ 也是一个约数。每个约数都是关于 $\sqrt n$ 对称的。还有完全平方数。因此只要扫描1~ $\sqrt n$ 的所有数将d和n/d作为约数加入到集合中就可以。

1.4求1~n每个数的正约数集合-倍数法

以d为正约数的数有 $d,2d,3d,4d....\lfloor n/d \rfloor*d$ 从1到n扫描每个数，将每个数的倍数的正约数集合都加入d。

1.5反素数

对于任何正整数x，其约数的个数记作g(x)，对于任意的0<i<x都满足g(i)<g(x)的数叫反素数。
性质1：其中1~ n中最大的反素数就是，1~n是约数最多的数中最小的一个。
性质2：不同质因数最多的数是10个因为 $2∗3∗5∗7∗11∗13∗17∗19∗23∗29∗31>2∗10^9$ ,且所有质因数的指数总和不超过30,因为 $2^{31}>2∗10^9$
性质3：将x分解成 $2^{c_1}∗3^{c_2}∗5^{c_3}∗7^{c_4}∗11^{c_5}∗13^{c_6}∗17^{c_7}∗19^{c_8}∗23^{c_9}∗29^{c_10}$ 后, $c_1\geq c_2\geq...\geq c_{10}$ 每个数的指数是单调递减，因为可以将这个质数指数与一个较小的质数的指数交换，交换完毕后，数变小，但是正约数个数不变。
有了这三个性质对每个质数的指数进行dfs搜索就可以了。
余数之和

#include<iostream>
using namespace std;
bool st[100];
int primes[100],cnt = 1;
int c[100];//储存每个质因子的个数
long long n,ans,k = 0;
void get_primes(int n){
    for(int i = 2;i < n;i++){
        if(!st[i]) primes[cnt++] = i;
        for(int j = 1;primes[j]*i < n;j++){
            st[i*primes[j]] = true;
            if(i%primes[j]==0) break;
        }
    }
}

void dfs(long long sum,long long count,int last){
    if(sum>n) return;
    if(count>k||(count==k&&sum<ans)) ans = sum,k = count;
    for(int i = last;i < 11;i++){
        if(c[i-1]>c[i]&&primes[i]*sum<=n){
            c[i]++;
            dfs(sum*primes[i],(count/c[i])*(c[i]+1),i);
            c[i]--;
        }
    }
}

int main(){
    get_primes(100);
    c[0] = 0xfffffff;
    cin>>n;
    dfs(1,1,1);
    cout<<ans<<endl;
}

1.6余数之和

给出正整数n和k，计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值。

例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7。
$k\pmod i = k - \lfloor k/i \rfloor *i$
$j(n, k) = nk - \sum_{i=1}^n \lfloor k/i \rfloor *i$
$\sum_{i=1}^n \lfloor k/i \rfloor$ 这个式子中k/i向下取整最多能取 $2*\sqrt{n}个数$ ，如果我们能确定每个数的范围，那么 $O(\sqrt n)$ 的时间就可以求出答案。
问题可以变为给出 $f(x) = \lfloor k/x \rfloor$ 求出满足f(x)不变时，x的取值范围。我们设x是f(x)的左边界，那么右边界是多少呢？
令 $f(x) = \lfloor k/x \rfloor$ , $g(x) = \lfloor k/f(x) \rfloor$
g(x)就是f(x)的右边界。可以理解为，我们先将k分为f(x)+1段，前x段每段长x,最后一段长度不固定,所有长度相加为k。我们要求最大的x。另每一段长度最大就是最后一段长度最小。其他位置均分k，分为f(x)段，并且我们要求的是取整数，所以x/f(x)需要向下取整。

#include<cstdio>
#include<iostream>
using namespace std;
int main(){
    long long n,k;
    cin>>n>>k;
    long long ans = n*k;
    for(long long x = 1,gx = 0;x <= n;x = gx+1){
        if(k/x==0) break;
        gx = min(k/(k/x),n);
        ans -= (k/x)*(gx + x)*(gx - x + 1)/2;
    }
    cout<<ans<<endl;
}

2最大公约数

自然数d同时是a,b的约数，称d是公约数，d是所有公约数中最大的数d就是最大公约数，记作 $gcd(a,b)$ 。
自然数m同时是a，b的倍数，称m是公倍数。m是所以公倍数中最小的数，那么m就是最小公倍数记作 $lcm(a,b)$ 。
定理： $\forall a，b \in \mathbb{N}$ 都有 $gcd(a,b)*lcm(a,b) = a*b$
证明： $d = gcd(a,b),lcm(a,b) = lcm(a/d,b/d)*d = a*b/d = a*b / gcd(a,b)$
更相减损术：
$\forall a，b \in \mathbb{N}，a\geq b$ 有 $gcd(a,b)=gcd(a-b,b)=gcd(a,a-b)$
$\forall a，b \in \mathbb{N},gcd(2a,2b) = 2gcd(a,b)$
证明：d是a，b的任意约数，那么 $d|a,d|b$ 所以 $d|(a-b)$ 所以这三个集合的公约数集合相等。
欧几里得算法：
$\forall a，b \in \mathbb{N}，b\neq 0$ , $gcd(a,b) = gcd(b,a\pmod b)$
证明：若a<b, $gcd(a,b) = gcd(b,a)$
若a>=b,令 $a = qb+r$ 其中 $0\leq r < b$ 显然r是 $a \pmod b$ 的约数。对于a，b任意公约数d。 $d|a,d|q*b$ 所以 $d|(a-qb)$ 因此d也是r的约数。

3互质与欧拉函数

定义： $\forall a,b \in \mathbb{N},$ 若 $gcd(a,b) =1,$ 则称a，b互质。gcd(a,b,c)称为a，b，c互质，而 $gcd(a,b)=gcd(b,c)=gcd(a,c)=1$ 称为两两互质。例如2,3,4互质但是不是两两互质。
欧拉函数
1~N中与N互质的数的个数被称为欧拉函数，记为 $\varphi(N)$ 。
欧拉函数的计算方法是对N分解 $N = p_1^{c_1}p_2^{c_2}...p_m^{c_m}$
$\varphi(N) = N * \frac{p_1 - 1}{p_1}* \frac{p_2 - 1}{p_2}* ...*\frac{p_m - 1}{p_m}$
对N个数，排除以p为质因子的数，得到的就是欧拉函数。

3.1欧拉函数的性质

性质1： $\forall n>1$ ，1~n中与n互质的数的和为 $n*\varphi(n)/2$
性质2：若a,b互质，则 $\varphi(ab) = \varphi(a)*\varphi(b)$
证明性质1：gcd(n,x) = gcd(n,n-x),所以与n互质的数是成对出现的分别为x和n-x平均值是 $\frac n 2$ 一共有 $\varphi(n)$ 个。
证明性质2：根据求欧拉函数的公式，直接带入等式。等式左右两边相等。
下面这个定义是积性函数的定义。
定义：如果当a，b互质时，有f(ab) = f(a)*f(b),那么称函数f为积性函数。
性质3欧拉函数满足，积性函数也满足。
性质3：若f是积性函数，且在算数基本定理中， $n = \prod_{i=1}^mp_i^{c_1}$ 则 $f(n) = \prod_{i=1}^m f(p_i^{c_1})$
性质4：设p为质数，若 $p|n$ 且 $p^2|n$ 则 $\varphi(n) = p*\varphi(n/p)$
性质5：设p为质数，若 $p|n$ 但 $p^2\nmid n$ 则 $\varphi(n) = (p-1)*\varphi(n/p)$
性质6： $\sum\nolimits_{d\mid n}\varphi(d) = n$
证明：首先看性质3直接代入求欧拉函数的公式即可，等式两边相等。
性质4，n/p包含质数p，n与n/p的质因数集合相同。求欧拉函数的公式中，只有N不同。从而可以推出关系。
性质5，n/p不包含质数p，n包含质数p。求欧拉函数的公式中，N不同，并且n/p比n少乘了一个 $\frac{p-1}{p}$
性质6：首先证明 $\sum\nolimits_{d\mid n}\varphi(d) = n$ 是积性函数。 $gcd(n,m)=1$ 令f代表这个公式。
$f(nm) = \sum\nolimits_{d\mid nm}\varphi(d) = \sum\nolimits_{d\mid n}\varphi(d) * \sum\nolimits_{d\mid m}\varphi(d)=f(n)*f(m)$
n与m互质，证明了f是积性函数。对于单个因此 $p^m$ 来说， $f(p^m) = \varphi(1)+\varphi(p)+\varphi(p^2)+...+\varphi(p^m) = p^m$
因此对于整个n分解为几个 $p_i^{c_i}$ 然后使用积性函数性质求出f(n)。