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;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/Tomori-Nao/sp32079