SP32079 ADAGF - Ada and Greenflies 题解
题目链接:SP32079 ADAGF - Ada and Greenflies
题意:
给定 \(a_i\) ,求 \[ \sum_{1\le i \le j \le n} \gcd(a_i,a_{i+1},\cdots,a_j) \] 数据范围:
\(1\le n \le 3\times 10^5,~0 \le a_i \le 10^6\) 。
很经典的题。我记得我第一次做好像是用二分做的,复杂度比现在的做法应该多一个 log 。
容易发现 \(j\) 固定时,区间 \([i,j]\) 的 \(\gcd\) 会单调递减。并且每次至少减少一半(除以 \(2\) )
所以实际上只有 \(\log M\) 段,于是我们可以动态地维护这个段,每段对 \(a_j\) 取 \(\gcd\) 。
时间复杂度 \(\mathcal{O}(n\log M)\) ,应该比二分快多了。
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e5 + 15))
#define Fi first
#define Se second
vector<pii> R[N]; int res,a[N];
int gcd(int x,int y) { return y == 0 ? x : gcd(y, x % y); }
void solve(int n)
{
for(int i = 1; i <= n; i++)
{
int x = a[i], pos = i;
for(int j = 0; j < R[i - 1].size(); j++)
{
pii lst = R[i - 1][j]; int tmp = gcd(x, lst.Se);
if(tmp != x) { R[i].emplace_back(pos,x); }
pos = lst.Fi; x = tmp;
}
R[i].emplace_back(pos, x);
for(int j = R[i].size() - 1; j; j--)
{
int l = R[i][j].Fi, r = R[i][j - 1].Fi;
int g = R[i][j].Se; res += (r - l) * g;
}
res += (i - R[i][0].Fi + 1) * R[i][0].Se;
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int n; cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
solve(n); cout << res << '\n';
return 0;
}
参考文献: