題目描述

　　Mirko剛學會了如何求兩個整數A和B的最大公約數。
　　由于A和B都非常大，所以我們不能直接給出，我們知道A是由N個正整數相乘得到的，我們也知道B是由M個正整數相乘得到的。
　　你的任務就是求A和B的最大公約數。
　　如果最大公約數超過9位，那么你只需要結果的后9位即可（如果后9位有前導0，則不需要輸出前導0）。

?

輸入輸出格式

輸入格式

　　第一行，一個整數N。(1 ≤ N ≤ 1000)。
　　第二行，N個正整數，這N個整數的乘積就等于A。每個正整數的范圍：【1，1000000000】.
　　第三行，一個整數M。(1 ≤ M ≤ 1000)。
　　第四行，M個正整數，這M個整數的乘積就等于B。每個正整數的范圍：【1，1000000000】.

?

輸出格式

　　A和B的最大公約數。如果超過9位，輸出后9位數字，如果后9位有前導0，則不需要輸出前導0。

?

輸入輸出樣例

輸入樣例

3
358572 83391967 82
3
50229961 1091444 8863

?

輸出樣例

12028

?

題解

　　這題a和b很大，所以不能直接用gcd。

　　我們知道，給定一個大于1的正整數$a$，滿足$a=\prod_{i=1}^{k}b_{i}^{p^{i}}$，那么我們可以分解題目中的a和b的質因數來求gcd。

#include <iostream> #include <algorithm>#define MAX_N (1000 + 5) #define MAX_M (1000 + 5) #define SQRT 32000using namespace std;const int mod = 1000000000; int n, m; int p[SQRT], cnt; int f[SQRT]; int a[SQRT], b[SQRT]; int c[MAX_N], d[MAX_M], totc, totd; int ans = 1;int main() {for(register int i = 2; i <= SQRT; ++i){if(f[i] ^ 1) p[++cnt] = i;for(register int j = 1; p[j] * i <= SQRT; ++j){f[p[j] * i] = 1;if(!(i % p[j])) break;}}int tmp;cin >> n;for(register int i = 1; i <= n; ++i){cin >> tmp;for(register int j = 1; j <= cnt && p[j] <= tmp; ++j){while(!(tmp % p[j])){tmp /= p[j];++a[p[j]];}}if(tmp != 1) c[++totc] = tmp;}cin >> m;for(register int i = 1; i <= m; ++i){cin >> tmp;for(register int j = 1; j <= cnt && p[j] <= tmp; ++j){while(!(tmp % p[j])){tmp /= p[j];++b[p[j]];}}if(tmp != 1) d[++totd] = tmp;}for(register int i = 2; i <= SQRT; ++i){for(register int j = min(a[i], b[i]); j; --j){ans = (long long)ans * i % mod;}}sort(c + 1, c + totc + 1);sort(d + 1, d + totd + 1);for(register int i = 1, j = 1; i <= totc && j <= totd;){if(c[i] < d[j]) ++i;else if(c[i] > d[j]) ++j;else ans = (long long)ans * c[i++] % mod, ++j;}cout << ans;return 0; } 參考程序

?

轉載于:https://www.cnblogs.com/kcn999/p/10585141.html

總結

以上是生活随笔為你收集整理的【题解】最大公约数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。