C. Orac and LCM

思路

題目非常簡單，就是求$gcd(lc{m}_{(}i,j))foriinrange(n),forjinrange(n),i<j$

對于包含$a_1$的項有，$gcd(lc{m}_{1,2},lc{m}_{1,3},lc{m}_{1,4},\dots \dots ，lc{m}_{1,n?1},lc{m}_{1,n})$

由于每一項都包含$a_1$，所以整體的$gcd=lcm(a_1,gcd(a_2,a_3,a_4,\dots \dots ,a_{n?1},a_n))$

同樣的其最后的$GCD$就是這$n$項的$gcd$的共同的$gcd$，通樣的對于所有的$gcd(a_i\dots \dots a_n)$我們可以通過對原數(shù)組從后開始求$gcd$，求得。

正確代碼

#include <bits/stdc++.h>using namespace std;typedef long long ll;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }const int N = 1e5 + 10;ll a[N], b[N]; int n;ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a; }ll lcm(ll a, ll b) {return a * b / gcd(a, b); }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);n = read();for(int i = 1; i <= n; i++)a[i] = read();for(int i = n; i >= 1; i--) b[i] = gcd(b[i + 1], a[i]);ll ans = 0;for(int i = 1; i <= n; i++)ans = gcd(ans, lcm(a[i], b[i + 1]));printf("%lld\n", ans);return 0; }

一個不會優(yōu)化的代碼

大概思路就是只有當一個質因子在最少n - 1個數(shù)中出現(xiàn)過，其對整體的$gcd$才有貢獻，所以我們只需要統(tǒng)計這些質因子出現(xiàn)的次數(shù)，一個質因子出現(xiàn)了$n?1$次，即是他的最小次方的出現(xiàn)項對整體有貢獻，如果一個數(shù)出現(xiàn)了$n$次，即是他的次二小次方項對整體有貢獻。

但是這個代碼的復雜度過高了，優(yōu)化不出來$O(200000?(200000以內的質數(shù)個數(shù)))$

#include<bits/stdc++.h>using namespace std;typedef long long ll; const int N = 2e5 + 10;int prime[N], n, cnt, flag[N]; vector<ll> num[N]; bool st[N];void init() {st[0] = st[1] = true;for(int i = 2; i < N; i++) {if(!st[i]) prime[cnt++] = i;for(int j = 0; j < cnt && prime[j] * i < N; j++) {st[i * prime[j]] = true;if(i % prime[j] == 0) break;}} }int main() {// freopen("in.txt", "r", stdin);scanf("%d", &n);init();int t;for(int i = 0; i < n; i++) {scanf("%d", &t);for(int j = 0; prime[j] <= t; j++) {ll sum = 1;while(t % prime[j] == 0) {t /= prime[j];sum *= prime[j];}if(sum != 1) {flag[j]++;num[j].push_back(sum);}}}ll ans = 1;for(int i = 0; i < cnt; i++) {if(flag[i] == n - 1) {sort(num[i].begin(), num[i].end());ans *= num[i][0];}if(flag[i] == n) {sort(num[i].begin(), num[i].end());ans *= num[i][1];}}printf("%lld\n", ans);return 0; }

總結

以上是生活随笔為你收集整理的C. Orac and LCM（数论lcm, gcd）的全部內容，希望文章能夠幫你解決所遇到的問題。

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