文章目錄
- 最大公約數GCD
- 最小公倍數LCM
- 擴充歐幾裡得
- 例題
-
- HDU-5223
- HDU-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;
} 複制
擴充歐幾裡得
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;
} 複制
- 求解不定方程
- 求解摸的逆元
- 求解同餘方程
例題
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; //初始化原數組1
for (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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 9973
ll 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;
} 複制
原創不易，請勿轉載（本不富裕的通路量雪上加霜 ）
部落客首頁：https://blog.csdn.net/qq_45034708