题目链接

acwing3642. 最大公约数和最小公倍数
acwing877. 扩展欧几里得算法
P4549 【模板】裴蜀定理

---

裴蜀定理:

1. 对于任意整数 \(a,b\),存在一对整数 \(x,y\)， 满足 ax+by=gcd(a,b)
2. \(ax+by=c,x∈Z^∗ ,y∈Z^ ∗\) 成立的充要条件是\({\gcd(a,b)|c}\)。\(Z^*\)表示正整数集。

[acwing3642. 最大公约数和最小公倍数

题目描述

输入两个正整数 \(m\) 和 \(n\)，求其最大公约数和最小公倍数。

输入格式

一行，两个整数 \(m\) 和 \(n\)。

输出格式

一行，输出两个数的最大公约数和最小公倍数。

数据范围

\(1≤n,m≤10000\)

输入样例：

5 7

输出样例：

1 35

代码

• 时间复杂度：\(O(a+b)\)

递归

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    printf("%d %d",gcd(n,m),n*m/gcd(n,m));
    return 0;
}

非递归

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int tmp=n*m;
    while(m^=n^=m^=n%=m);
    printf("%d %d",n,tmp/n);
    return 0;
}

acwing877. 扩展欧几里得算法

题目描述

给定 \(n\) 对正整数 \(a_i,b_i\)，对于每对数，求出一组 \(x_i,y_i\)，使其满足 \(a_i×x_i+b_i×y_i=gcd(a_i,b_i)\)。

输入格式

第一行包含整数 \(n\)。

接下来 \(n\) 行，每行包含两个整数 \(a_i,b_i\)。

输出格式

输出共 \(n\) 行，对于每组 \(a_i,b_i\)，求出一组满足条件的 \(x_i,y_i\)，每组结果占一行。

本题答案不唯一，输出任意满足条件的 \(x_i,y_i\) 均可。

数据范围

\(1≤n≤10^5, 1≤a_i,b_i≤2×10^9\)

输入样例：

2
4 6
8 18

输出样例：

-1 1
-2 1

代码

• 时间复杂度：\(O(a+b)\)

#include<bits/stdc++.h>
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int z=x;
    x=y,y=z-y*(a/b);
    return d;
}
int main()
{
    int t;
    for(scanf("%d",&t);t;t--)
    {
        int a,b,x,y;
        scanf("%d%d",&a,&b);
        exgcd(a,b,x,y);
        printf("%d %d\n",x,y);
    }
    return 0;
}

[P4549 【模板】裴蜀定理]

题目描述

给定一个包含 \(n\) 个元素的整数序列 \(A\)，记作 \(A_1,A_2,A_3,...,A_n\) 。

求另一个包含 \(n\) 个元素的待定整数序列 \(X\)，记 \(S=\sum\limits_{i=1}^nA_i\times X_i\)，使得 \(S>0\) 且 \(S\) 尽可能的小。

输入格式

第一行一个整数 \(n\)，表示序列元素个数。

第二行 \(n\) 个整数，表示序列 \(A\)。

输出格式

一行一个整数，表示 \(S>0\) 的前提下 \(S\) 的最小值。

输入

2
4059 -1782

输出

99

说明/提示

对于 \(100\%\) 的数据，\(1 \le n \le 20\)，\(|A_i| \le 10^5\)，且 \(A\) 序列不全为 \(0\)。

代码

• 时间复杂度：\(O(\sum{a_i})\)

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,res,other;
    scanf("%d%d",&n,&res);
    while(--n)
    {
        scanf("%d",&other);
        res=__gcd(res,other);
    }
    printf("%d",abs(res));
    return 0;
}