约数相关

xiejinhao · 2019-07-07 13:31:03 · 个人记录

约数

约数简介

定义：

若整数 n 除以整数 d 的余数为 0，即 d 能整除 n， 则称 d 是 n，的约数，n 是 d 的倍数，记为 d|n

在算术基本定理中 N可被分解成下面这个样子

N=\prod_{i=1}^m p_i^ {c_i}, \ p_1<p_2<…<p_m , \ c_i ∈ N^*

那么N的正约数个数为：

(c_i+1)*(c_i+2)*…(c_m+1)=\prod_{i=1}^{m}(c^i+1)

$$\prod_{i=1}^{m}{(\sum_{j=0}^{c^i}(p_i)^j)}$$ ### 求解$N$的正约数集合 - 试除法 $ \ \ \ \ \ \ $如果一个数$x$是$N$的约数，那么$N/d≤\sqrt N$也为$N$的约数。 $ \ \ \ \ \ \ $因为约数总是成对出现，因此扫描 $x=1-\sqrt N \ ∈Z$，尝试是否 $x|N$。但是我们要特判完全平方数，因为对于完全平方数$\sqrt N \ ∈Z$。 ```cpp int factor[1600], num = 0; for(int i = 1; i * i <= n; i++) { if(n % i == 0) { factor[++num] = i; if(i != n/i) factor[++num] = n / i; } } ``` $ \ \ \ \ \ \ $求$1-\sqrt N$每个数的正约数集合——倍数法基本思想： $ \ \ \ \ \ \ $不同于试除法，我们可以反过来考虑每个数$x$,则以$x$为约数的数就是$x,2x,3x…

    vector<int> factor[SIZE];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n / i; j++)
            factor[i*j].push_back(i);       
    //输出
    for(int i = 1; i <= n ;i++) {
        for(int j = 0; j < factor[i].size; j++)
            printf("%d ",factor[i][j]);
        putchar('\n'); 
    }

\ \ \ \ \ \ $在小数据内($N∈[4,16]$)，试除法是要快于倍数法的，复杂度为$O(N\sqrt N)

约数相关内容：

1.最大公约数|gcd

定义：

$ \ \ \ \ \ \ $同理，若同时满足$a|x$和$b|x$，则$x$是$a$和$b$的公倍数，在这样的$x$中最小的一个，为$a,b$的最小公倍数，记为$lcm(a,b)$。 **定理：** $$∀a,b∈N, \ \ \ \ \ \ \ gcd(a,b)*lcm(a,b)=a*b $$ 以上定义的证明读者可以自行尝试，也可以《参考算法竞赛进阶指南》 - **求解方法** 在[浅谈质因数分解](https://www.luogu.org/blog/Ning-H/prime-factorization)中我们已经提到了求解$gcd$的算法：1.更相减损术 2.辗转相除法。 **《九章算术》有：** $$∀a,b∈N,a≥b,\ \ gcd(a,b)=gcd(b,a-b)=gcd(a,a-b)$$ $$∀a,b∈N,\ \ gcd(2a,2b)=2gcd(a,b)$$ 以上两条定理很重要，这涉及我们后面的二进制优化$gcd

欧几里得算法：

∀a,b∈N,b≠0,\ \ \ \ \ gcd(a,b)=gcd(b,a \ mod \ b)

这样就得出了我们熟悉的辗转相除法：

    //递归形式
    int gcd(int a, int b) {
        return b ? gcd(b, a % b) : a;
    } 

    //非递归形式
    int gcd(int a, int b) {
        int temp;
        while(b) {
            temp=a % b;
            a = b;
            b = temp;
        }   
        return a;
    }

$ \ \ \ \ \ \ $当然，$gcd$还可以优化(就是前面提到的二进制优化)。 - 为什么可以优化？因为辗转相除法运用了模运算，这样常数大运行慢，故用更相减损+二进制优化$gcd

a=0, \ return \ b; \ \mid \ b=0, \ return \ a;
a$ & $1$ 且 $b$ & $1$，$ \ ans=2gcd(a >> 1,b>>1);
a$ & $1$ 且！$b$ & $1$，$ \ ans=gcd(a >> 1,b);
！a & 1 且 b & 1， \ ans=gcd(a,b >> 1);
！a & 1 且！b & 1， \ ans=gcd(a - b,b)。

    //下面代码返回gcd(a,b)的值同时把b赋予这个值，不需要可以把&去掉
    int gcd(int a,int &b) {
        if(a == 0 || b == 0) return b = a + b; 
        int n = 0, m = 0;
        for(; !(a & 1); a >>= 1, n++); 
        for(; !(b & 1); b >>= 1, m++);
        n = m < n ? m : n;
        while(a) {
            if(a < b) { a ^= b, b ^= a, a ^= b;}
            if(!(a -= b)) return b <<= n;
            while(!(a & 1)) a >>= 1;
        }
    }

但注意上面代码在负数的时候是错误的，因为负数的右移1位和除2出不一样的，所以遇到负数时上面的位运算要用正常除法代替。

2.互质与欧拉函数

定义：

对于三个数及以上的情况类比即可，这里不再赘述，读者可以自行查阅相关资料。 **欧拉函数** $ \ \ \ \ \ \ $ $1-N$中与$N$互质的个数被称为欧拉函数，记为$φ(N)$。在算数基本定理中，$N=\prod_{i=1}^m p_i^ {c_i}$，则： $$φ(N)=N*\frac{1-p_1}{p_1}*\frac{1-p_2}{p_2}*\frac{1-p_3}{p_3}*…*\frac{1-p_m}{p_m}=N*\prod_{prime \ p|N}(1-\frac{1}{p})$$ 根据欧拉函数的计算式，我们只需要分解质因数，即可求出欧拉函数： ```cpp //参考代码(源于《算法竞赛进阶指南》) int phi(int n) { int ans = n; for(int i = 2; i <= sqrt(n); i++) if(n % i == 0) { ans = ans / i * (i - 1); while(n % i == 0) n /= i; } if(n > 1) ans = ans / n * (n - 1); return ans; } ``` - **欧拉函数的性质：** 1. $∀n>1,1-n$中与$n$互质的数和为$n*φ(n)/2$。 1. 若$gcd(a,b)=1$，即$a,b$互质，则$φ(ab)=φ(a)φ(b)$。 1. 设$p$为质数，若$ \ p \mid n \ $且$ \ p^2 \mid n$，则$φ(n)=φ(n/p)*p$。 1. 设$p$为质数，若$ \ p \mid n \ $且$ \ p^2 \nmid n$，则$φ(n)=φ(n/p)*(p-1)$。 1. $\sum_{d \mid n}φ(d)=n$。 **积性函数：** $ \ \ \ \ \ \ $ 如果$gcd(a,b)=1$，有$f(ab)=f(a)f(b)$，那么称函数$f$为积性函数 6. 若$f$是积性函数，且在算术基本定理中$n=\prod_{i=1}^m p_i^ {c_i}$，则$ \ f(n)=\prod_{i=1}^m f(p_i^ {c_i})$。（第六点同为欧拉函数的性质） **$*$完全积性函数：** $$∀a,b∈Z, \ \ \ \ \ \ \ f(ab)=f(a)f(b)$$ 关于积性函数的拓展非常多，内容也比较深奥，下面简单介绍下：常用积性函数如下 1. $φ(n)$ —— 欧拉函数 1. $σ(n)$ —— 约数和函数 1. $μ(n)$ —— 莫比乌斯函数 1. $σ_0(n)$ —— 约数个数函数 1. $σ_k(n)$ —— 约数次数和函数 1. $gcd(n,k)$ —— 最大公约数函数，当$k$固定时 1. $1(n)=1$ ——这个我也不知道是什么 1. $f(n)=n$——我还是不知道是什么 $ \ \ \ \ \ \ $**还有一点，就是积性函数都是可以线性筛的** - **狄利克雷卷积** 首先先补充下**数论函数**的定义： 1. 陪域：包含值域的任意集合 1. 数论函数：定义域为正整数，陪域为复数的函数好了，我们可以开始介绍**狄利克雷卷积**了。定义$f,g$为数论函数，则它们的狄利克雷卷积可以表示为$f*g$，设$h=f*g$： $$h(n)=\sum _{d|n}f(d)g\Big(\frac{n}{d}\Big)$$ 若$f,g$是积性函数，显然，$h$也是积性函数。 **证明** $ \ \ \ \ $设$n = a*b$且$a,b$互质，即$gcd(a,b)=1$： $$h(n)=\sum _{d_1|a, d_2|b}f(d_1d_2)g\Big(\frac{a}{d_1}\frac{b}{d_2}\Big)$$ $$=\sum_{d_1|a, d_2|b}f(d_1)f(d_2)g\Big(\frac{a}{d_1}\Big)g\Big(\frac{b}{d_2}\Big)$$ $$=\sum_{d_1|a}f(d_1)g\Big(\frac{a}{d_1}\Big)\sum_{d_2|b}f(d_2)g\Big(\frac{b}{d_2}\Big)$$ $$=h(a)*h(b)$$ $ \ \ \ \ $证毕。 **运算法则** 狄利克雷卷积的运算满足： 1. $f*g=g*f$（交换律） 1. $(f*g)*h=f*(g*f)$（结合律） 1. $f*(g+h)=f*g+f*h$（分配律） 1. 若$f,g$是积性函数，则$f*g$也是积性函数。（性质） **狄利克雷卷积相关** ------------ 下面还是回到欧拉函数： $ \ \ \ \ \ \ $我们可以利用 $Eratosthenes$ 筛法，按照欧拉函数的计算式，在$O(NlogN)$时间内求解出 $2-N$中每个数的欧拉函数。 ```cpp int phi[SIZE]; void eluer(int n) { for(int i = 2; i <= n; i++) phi[i] = i; for(int i = 2; i <= n; i++) if(phi[i] == i) for(int j = i; j <= n; j += i;) phi[j] = phi[j] / i * (i - 1); } ``` $ \ \ \ \ \ \ $但是既然说了积性函数都是可以线性筛的，那么欧拉函数如何优化成线性的呢？让我们来回顾质数线性筛的思想([质数筛法详解](https://www.luogu.org/blog/Ning-H/post-1-post))，线性筛中，每个合数$n$只会被它的质因子筛一次，利用下面几条性质： 1. 定理三：设$p$为质数，若$ \ p \mid n \ $且$ \ p^2 \mid n$，则$φ(n)=φ(n/p)*p$。 1. 定理四：设$p$为质数，若$ \ p \mid n \ $且$ \ p^2 \nmid n$，则$φ(n)=φ(n/p)*(p-1)

我们就可以在筛选合数时运用这两条定理，从φ(n/p)递推到φ(n)。

关于质数筛法，因为有两种线性筛的写法，其实是大同小异的，但是为了读者方便，这里都给出：

    //法一 ： 
    int v[SIZE], pri[SIZE], phi[SIZE], num;
    void promoted_eluer(int n) {
        for(int i = 2; i <= n; i++) {
            if(v[i] == 0) 
                pri[++num] = i, phi[i] = i - 1;
            for(int j = 1; j <= num && i * pri[j] <=n; j++) {
                v[i * pri[j]] = 1;
                phi[i * pri[j]]=
                  phi[i] * (i % pri[j] ? pri[j] - 1 : pri[j]);
                if(i % pri[j] == 0) break;
            }
        }
    }

    //法二： 
    int v[SIZE], pri[SIZE], phi[SIZE], num;
    void promoted_eluer(int n) {
        for(int i = 2; i <= n; i++) {
            if(v[i] == 0) 
                pri[++num] = i, phi[i] = i - 1, v[i] = i;
            for(int j = 1; j <= num; j++) {
                if(pri[j] > v[i] || pri[j] > n / i) break;
                v[i * pri[j]] = pri[j];
                phi[i * pri[j]]=
                  phi[i] * (i % pri[j] ? pri[j] - 1 : pri[j]);
            }
        }
    }

※章末练习

P1029 最大公约数和最小公倍数问题
P2205 [USACO13JAN]画栅栏Painting the Fence
UVA12716 GCD等于XOR GCD XOR
P2303 [SDOi2012]Longge的问题
UVA10791 最小公倍数的最小和 Minimum Sum LCM
P1072 Hankson 的趣味题
P2261 [CQOI2007]余数求和
P2520 [HAOI2011]向量
P2152 [SDOI2009]SuperGCD
P1463 [POI2002][HAOI2007]反素数
P2455 [SDOI2006]线性方程组
P3213 [HNOI2011]勾股定理
P3327 [SDOI2015]约数个数和
P3166 [CQOI2014]数三角形
P2500 [SDOI2012]集合
P2086 [NOI2012]魔幻棋盘
P3307 [SDOI2013]项链

END

PS:

以上讲解顺序及内容参考：李煜东《算法竞赛进阶指南》