Sum of Subarray GCDs
National Olympiad — National round
Submission name: trendy.cpp
Problem summary
For every nonempty contiguous subarray, compute the greatest common divisor of its values. Sum all these GCDs.
Input
N followed by N values.
Output
The sum modulo 1000000007.
Constraints
1 ≤ N ≤ 200000; 1 ≤ ai ≤ 10^9; memory limit 3 MB; published time limit 0.1 seconds.
Worked example
An independently prepared example for this explanation.
Input
3 2 4 8
Output
22
Solution analysis
- Stream values and maintain distinct GCDs of subarrays ending at the previous position, each with its multiplicity.
- For new x, start a singleton group (x,1). Transform every old group g into gcd(g,x), merging adjacent equal results.
- Add value times multiplicity for every new group to the answer. Each distinct decrease of a positive GCD at least halves it.
Why it works
All subarrays ending here are either the singleton or a unique previous subarray extended by x. Grouping equal GCDs preserves their counts.
Complexity: O(N log² A) worst-case arithmetic time using Euclid; O(log A) auxiliary space.
Watch out. Subarrays are contiguous. Streaming and compressed groups are essential for the small memory limit.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: All subarrays ending here are either the singleton or a unique previous subarray extended
// by x. Grouping equal GCDs preserves their counts.
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<tuple>
#include<numeric>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
const long long P=1000000007;
vector<pair<int,long long>>v,w;
long long ans=0;
while(n--){
int x;
cin>>x;
w.clear();
w.push_back({x,1});
for(auto[g,c]:v){
int z=gcd(g,x);
if(w.back().first==z){
w.back().second+=c;
}
else{
w.push_back({z,c});
}
}
for(auto[g,c]:w){
ans=(ans+g*c)%P;
}
v.swap(w);
}
cout<<ans<<'\n';
}