SP32079 ADAGF - Ada and Greenflies

· · 题解

题传

无聊水水经验

题意：求

\sum_{i=1}^{n}\sum_{j=i}^n \gcd_{i\le k \le j}\{a_k\}

考虑枚举 j，看它左边的 i 产生的所有点对的贡献。

不难发现，以 j 为右端点往左的全部 \gcd 必然单调，因为 i, j \ge \gcd(i, j)，并且能分成很多内部全部相等的段。

那么段数是多少呢？因为每当 \gcd 产生变化时其至少减半，所以最多只有 \log w 段的！

有了这个结论后，我们直接考虑增量计算，每次直接继承 j-1 的段数，然后每段直接对 a_j 取 \gcd，然后暴力合并，最后算贡献。

复杂度分析：每次至少让序列中的一个数减半，所以复杂度 O(n\log w)。

Code

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cctype>
#include <vector>
#include <cstdlib>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
//const int mo=998244353;
inline int read(){
    char ch=getchar();int x=0, f=1;
    while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
inline void write(int x){
    if(x<0) putchar('-'), x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int N=5e5+10;
vector < pair<int, int> > R[N];
int a[N];
int gcd(int x, int y){
    return y?gcd(y, x%y):x;
}
long long ans;
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){
            pair <int, int> lst=R[i-1][j];
            int tmp=gcd(x, lst.second);
            if(tmp!=x) R[i].push_back(make_pair(pos, x));
            pos=lst.first;x=tmp;
        }
        R[i].push_back(make_pair(pos, x));
        int up=R[i].size();
        for(int j=up-1; j; --j){
            int l=R[i][j].first, r=R[i][j-1].first;
            int g=R[i][j].second;
            long long gx=1ll*(r-l)*g;
            ans=(ans+gx);
        }
        int l=R[i][0].first, g=R[i][0].second;
        long long gx=1ll*(i-l+1)*g;
        ans=(ans+gx);
    }
}
signed main(){
    int n; scanf("%d",&n);
    for(int i=1; i<=n; ++i) scanf("%d",&a[i]);
    solve(n);printf("%lld", ans);
    return 0;
}