被一道水题给锤爆了
题面
题目链接
https://abc125.contest.atcoder.jp/tasks/abc125_c
题目大意
黑板上写着 N 个整数 A1 , A2 , ... , AN
您将选择其中之一，并用您选择的 1 到 1e9 之间的整数替换它，该整数可能与原始写入的整数相同。
替换后，在黑板上找到 N 个整数的最大可能的最大公约数。
解题思路
假设我们要替换的数为 ai
gcd1 = gcd[1 , i - 1] , gcd2 = gcd[i + 1 , n]
gcd1 和 gcd2 都是一定的，gcd3 = gcd(gcd1 , gcd2) 也是一定的
而不论 ai 替换成什么 ans = gcd(a[i] , gcd3) 的值都只可能小于等于 gcd3
所以我们只要维护 gcd 前缀和后缀，再遍历一遍即可
AC_Coder
#include<bits/stdc++.h> using namespace std; const int N = 2e5 + 10; int gcd(int a , int b) { return b ? gcd(b , a % b) : a; } int a[N] , pre[N] , suf[N]; signed main() { int n; cin >> n; for(int i = 1 ; i <= n ; i ++) cin >> a[i]; for(int i = 1 ; i <= n ; i ++) { pre[i] = gcd(pre[i - 1] , a[i]); suf[n - i + 1] = gcd(suf[n - i + 2] , a[n - i + 1]); } int ans = 1; for(int i = 1 ; i <= n ; i ++) ans = max(ans , gcd(pre[i - 1] , suf[i + 1])); cout << ans << 'n' ; return 0; }
原文链接: https://www.cnblogs.com/GsjzTle/p/12843413.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/346995
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
