数论-GCD LCM 扩展欧几里得

文章目录

最大公约数GCD最小公倍数LCM扩展欧几里得例题HDU-5223HDU-1576

最大公约数GCD

---

欧几里得算法（辗转相除法）求GCD

int gcd(int x, int y) {return y == 0 ? x : gcd(y, x % y);}

最小公倍数LCM

---

int lcm(int x, int y) {return x / gcd(x, y) * y;}

扩展欧几里得

---

问题引入： a x + b y = n ax+by=n ax+by=n什么时候有整数解？有解的充要条件是 g c d ( a , b ) gcd(a,b) gcd(a,b)可以整除 n n n，当方程符合 a x + b y = g c d ( a , b ) ax+by=gcd(a,b) ax+by=gcd(a,b)时，可以用扩展欧几里得算法求一个整数解 ( x 0 , y 0 ) (x_0,y_0) (x0​,y0​)，程序如下：

ll extend_gcd(ll a, ll b, ll& x, ll& y) {if (b == 0) {x = 1; y = 0;return a;}ll gcd = extend_gcd(b, a % b, y, x);y -= x * (a / b);return gcd;}

得到 ( x 0 , y 0 ) 后 ， (x_0,y_0)后， (x0​,y0​)后，进而推出方程 a x + b y = n ax+by=n ax+by=n的一个解 ( x 0 ′ , y 0 ′ ) ， x 0 ′ = x 0 n / g c d ( a , b ) ， y 0 ′ = y 0 n / g c d ( a , b ) (x_0',y_0')，x_0'=x_0n/gcd(a,b)，y_0'=y_0n/gcd(a,b) (x0′​,y0′​)，x0′​=x0​n/gcd(a,b)，y0′​=y0​n/gcd(a,b)。

扩展欧几里得应用：

求解不定方程求解摸的逆元求解同余方程

例题

---

HDU-5223

HDU-5223 GCD

Problem Description

In mathematics, the greatest common divisor (gcd) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4.—Wikipedia

BrotherK and Ery like playing mathematic games. Today, they are playing a game with GCD.

BrotherK has an array A with N elements: A1 ~ AN, each element is a integer in [1, 10^9]. Ery has Q questions, the i-th question is to calculate

GCD(ALi, ALi+1, ALi+2, …, ARi), and BrotherK will tell her the answer.

BrotherK feels tired after he has answered Q questions, so Ery can only play with herself, but she don’t know any elements in array A. Fortunately, Ery remembered all her questions and BrotherK’s answer, now she wants to recovery the array A.

Input

The first line contains a single integer T, indicating the number of test cases.

Each test case begins with two integers N, Q, indicating the number of array A, and the number of Ery’s questions. Following Q lines, each line contains three integers Li, Ri and Ansi, describing the question and BrotherK’s answer.

T is about 10

2 ≤ N Q ≤ 1000

1 ≤ Li < Ri ≤ N

1 ≤ Ansi ≤ 109

Output

For each test, print one line.

If Ery can’t find any array satisfy all her question and BrotherK’s answer, print “Stupid BrotherK!” (without quotation marks). Otherwise, print N integer, i-th integer is Ai.

If there are many solutions, you should print the one with minimal sum of elements. If there are still many solutions, print any of them.

Sample Input

2

2 2

1 2 1

1 2 2

2 1

1 2 2

Sample Output

Stupid BrotherK!

2 2

给定若干区间的GCD，试还原原数组。

贪心乘最小的数使得区间内每个数是ans[i]的倍数(LCM)，最后再检查一遍。

#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1003;ll t, n, q;ll a[maxn], l[maxn], r[maxn], ans[maxn];ll gcd(ll x, ll y) {return y == 0 ? x : gcd(y, x % y);}ll lcm(ll x, ll y) {return x / gcd(x, y) * y;}int main() {cin >> t;while (t--) {cin >> n >> q;for (int i = 1; i <= n; i++)a[i] = 1; //初始化原数组1for (int i = 1; i <= q; i++) {cin >> l[i] >> r[i] >> ans[i];for (int j = l[i]; j <= r[i]; j++)a[j] = lcm(a[j], ans[i]);}bool tag = true;for (int i = 1; i <= q; i++) {//检验ll tmp = a[l[i]];for (ll j = l[i] + 1; j <= r[i]; j++)tmp = gcd(tmp, a[j]);if (tmp != ans[i]) {tag = false;break;}}if (tag) {cout << a[1];for (int i = 2; i <= n; i++)cout << " " << a[i];cout << "\n";}else cout << "Stupid BrotherK!\n";}return 0;}

HDU-1576

HDU-1576 A/B

Problem Description

要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。

Input

数据的第一行是一个T，表示有T组数据。

每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。

Output

对应每组数据输出(A/B)%9973。

Sample Input

2

1000 53

87 123456789

Sample Output

7922

6060

令 m = 9973 , x = a / b ， 则 a = b x 令m=9973,x=a/b，则a=bx 令m=9973,x=a/b，则a=bx

又 n = a % m , 所 以 n = a − a / m ∗ m 又n=a\%m,所以n=a-a/m*m 又n=a%m,所以n=a−a/m∗m

b x 代 入 a , n = b x − b x / m ∗ m bx代入a,n=bx-bx/m*m bx代入a,n=bx−bx/m∗m

设 x 1 = x , y 1 = b x / m , 则 n = b x 1 − y 1 m 设x_1=x,y_1=bx/m,则n=bx_1-y_1m 设x1​=x,y1​=bx/m,则n=bx1​−y1​m

两 边 除 n , b x 1 n − y 1 m n = 1 ， 即 b x 2 − m y 2 = 1 两边除n,\frac{bx_1}{n}-\frac{y_1m}{n}=1，即bx_2-my_2=1 两边除n,nbx1​​−ny1​m​=1，即bx2​−my2​=1

又 因 为 g c d ( b , m ) = 1 , 所 以 b x 2 − m y 2 = g c d ( b , m ) 又因为gcd(b,m)=1,所以bx_2-my_2=gcd(b,m) 又因为gcd(b,m)=1,所以bx2​−my2​=gcd(b,m)

所以通过扩展欧几里得求得的最小特解 x 2 x_2 x2​， x 2 x_2 x2​乘 n n n得 x 1 x_1 x1​，最后处理下取余负数即可。

#include<bits/stdc++.h>using namespace std;typedef long long ll;#define mod 9973ll t, n, a, b, x, y;ll extend_gcd(ll a, ll b, ll& x, ll& y) {if (b == 0) {x = 1; y = 0;return a;}ll gcd = extend_gcd(b, a % b, y, x);y -= x * (a / b);return gcd;}int main() {cin >> t;while (t--) {cin >> n >> b;extend_gcd(b, mod, x, y);x *= n;x = (x % mod + mod) % mod;cout << x << "\n";}return 0;}

原创不易，请勿转载（本不富裕的访问量雪上加霜）

博主首页：/qq_45034708

如果文章对你有帮助，记得关注点赞收藏❤