0x32.数学知识 - 约数

目录

• 一、约数
• 二、最大公约数
• 三、互质与欧拉函数

声明：
本系列博客是《算法竞赛进阶指南》+《算法竞赛入门经典》+《挑战程序设计竞赛》的学习笔记，主要是因为我三本都买了 按照《算法竞赛进阶指南》的目录顺序学习，包含书中的少部分重要知识点、例题解题报告及我个人的学习心得和对该算法的补充拓展，仅用于学习交流和复习，无任何商业用途。博客中部分内容来源于书本和网络（我尽量减少书中引用），由我个人整理总结（习题和代码可全都是我自己敲哒）部分内容由我个人编写而成，如果想要有更好的学习体验或者希望学习到更全面的知识，请于京东搜索购买正版图书：《算法竞赛进阶指南》——作者李煜东，强烈安利，好书不火系列，谢谢配合。

---

下方链接为学习笔记目录链接（中转站）

学习笔记目录链接

---

ACM-ICPC在线模板

---

一、约数

定义

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

算术基本定理的推论

由算数基本定理得正整数N可以写作 N = p 1 C 1 × p 2 C 2 × p 3 C 3 ⋯ × p m C m N=p_1^{C_1}\times p_2^{C_2} \times p_3^{C_3} \cdots \times p_m^{C_m} N=p1C1​​×p2C2​​×p3C3​​⋯×pmCm​​

N的正约数个数为( Π Π Π是连乘积的符号，类似 ∑ ∑ ∑)

( c 1 + 1 ) × ( c 2 + 1 ) × ⋯ ( c m + 1 ) = Π i = 1 m ( c i + 1 ) (c_1+1)\times (c_2+1)\times \cdots (c_m+1)=\Pi_{i=1}^{m}(ci+1) (c1​+1)×(c2​+1)×⋯(cm​+1)=Πi=1m​(ci+1)
N的所有正约数和为

( 1 + p 1 + p 1 2 + ⋯ + p 1 c 1 ) × ⋯ × ( 1 + p m + p m 2 + ⋯ + p m c m ) = ∏ i = 1 m ( ∑ j = 0 c i ( p i ) j ) (1+p_1+p_1^2+\cdots +p_1^{c_1})\times\cdots\times(1+p_m+p_m^2+\cdots +p_m^{c_m})=\prod_{i=1}^{m}(\sum_{j=0}^{c_i}(p_i)^j) (1+p1​+p12​+⋯+p1c1​​)×⋯×(1+pm​+pm2​+⋯+pmcm​​)=i=1∏m​(j=0∑ci​​(pi​)j)

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

约数总是成对出现，所以只需要枚举到 n \sqrt{n} n ​即可。（除了完全平方数，只有一个 n \sqrt{n} n ​）

vector<int>factor;
int m;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i * i <= n; ++ i){
        if(n % i == 0){
            factor.push_back(i);
            if(i != n / i)
                factor.push_back(n / i);
        }
    }
    for(int i = 0; i < factor.size(); ++ i){
        printf("%d\n", factor[i]);
    }
    return 0;
}

推论：一个整数N的约束个数上界为 2 n \tt 2\sqrt{n} 2n ​

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

时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)（每一个约数为 O ( 1 ) O(1) O(1)总共 n l o g n nlogn nlogn个）

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i){
        for(int j = 1 ;j * i <= n; ++ j){
            factor[i * j].push_back(j);
        }
    }
    for(int i = 1; i <= n; ++ i){
        cout << i << ": ";
        for(int j = 0; j < factor[i].size(); ++ j)
            printf("%d ", factor[i][j]);
        puts("");
    }
    return 0;
}

推论：1~N中每个数的约数的总和大概为 N l o g N NlogN NlogN。

AcWing198. 反素数

二、最大公约数

最大公约数与最大公倍数

最多 O ( l o g n ) O(logn) O(logn)

int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
}

int lcm(int a,int b){
	return a / gcd(a,b) * b;//先除后乘，以免溢出
}

更相减损术

∀ a , b ∈ N , a > b , 有 g c d ( a , b ) = g c d ( b , a − b ) = g c d ( a , a − b ) ∀ a , b ∈ N , 有 g c d ( 2 a , 2 b ) = 2 g c d ( a , b ) \forall a,b \in N , a > b,有gcd(a,b)=gcd(b,a-b)=gcd(a,a-b) \\ \forall a,b \in N , 有gcd(2a,2b) = 2gcd(a,b) ∀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)

luogu P1072 （NOIP2009）Hankson的趣味题

∵ l c m ( a , b ) × g c d ( a , b ) = a × b ∴ l c m ( x , c ) = d ⇔ d × g c d ( x , c ) = x × c \because lcm(a,b)\times gcd(a,b)=a\times b\\ \therefore lcm(x,c)=d\Leftrightarrow d\times gcd(x,c)= x \times c ∵lcm(a,b)×gcd(a,b)=a×b∴lcm(x,c)=d⇔d×gcd(x,c)=x×c

int a, b, c, d;
int ans;

int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}
int t;
int main()
{
    scanf("%d", &t);
    while(t -- ){
        ans = 0;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        for(int x = 1, y; x * x <= d; ++ x){
            if(d % x)continue;
            if(gcd(x, a) == b && d * gcd(x, c) == x * c)
                ans ++ ;
            y = d / x;//另一个约数
            if(x == y)continue;
            if(gcd(y, a) == b && d * gcd(y, c) == y * c)
                ans ++ ;
        }
        printf("%d\n", ans);
    }
    return 0;
}

三、互质与欧拉函数