Dynamic Subset GCD Sum
National Olympiad — National round (2022 season)
Submission name: gcd2.cpp
Problem summary
Maintain a set of distinct positive integers under insertion and deletion. Print the sum of gcds of all nonempty subsets, modulo 1000000007, initially and after every update.
Input
N Q, the N initial values, then Q lines t x: t=1 inserts absent x; t=2 deletes present x.
Output
Q+1 modular sums, one per line.
Constraints
0 ≤ N,Q ≤ 200000; 1 ≤ values ≤ 2000000; updates preserve set semantics.
Worked example
An independently prepared example for this explanation.
Input
3 3 2 4 8 2 2 1 16 1 39
Output
24 16 48 94
Solution analysis
- Use the identity g=Σ(phi(d): d divides g). If count[d] elements of the current set are divisible by d, then 2^count[d]−1 nonempty subsets have all elements divisible by d. Exchanging the two sums gives answer=Σ phi(d)*(2^count[d]−1).
- Inserting x changes only divisors d of x. Increasing a count from c to c+1 increases its contribution by phi(d)*2^c. Deletion first decreases the count and subtracts phi(d)*2^newCount. Precompute totients, smallest prime factors, and powers of two.
- For {2,4,8}, counts for divisors 1,2,4,8 are 3,3,2,1. Their contributions are 7,7,6,4, totaling 24. Deleting 2 removes contributions phi(1)*2²+phi(2)*2²=8, leaving 16.
Why it works
The totient identity decomposes each subset gcd into exactly its divisor contributions. A subset contributes phi(d) exactly when every selected value is divisible by d, which occurs for precisely 2^count[d]−1 nonempty subsets. The insertion and deletion deltas are algebraic differences of this exact expression, so maintaining them preserves the correct answer after every operation.
Watch out. Deleting uses the power after decrementing its count. Normalize subtraction modulo 1000000007. Enumerate every divisor once, including 1 and x; there is no contribution from the empty subset.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
// Algorithm: Use the identity g=Σ(phi(d): d divides g).
using namespace std;
const int LIMIT=2000000;
const long long MODULUS=1000000007;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<int>phi(LIMIT+1),smallest(LIMIT+1,0),count(LIMIT+1,0);
for(int i=0;i<=LIMIT;++i){
phi[i]=i;
}
for(int prime=2;prime<=LIMIT;++prime){
if(smallest[prime]==0){
for(int multiple=prime;multiple<=LIMIT;multiple+=prime){
phi[multiple]-=phi[multiple]/prime;
if(smallest[multiple]==0){
smallest[multiple]=prime;
}
}
}
}
int n,q;
cin>>n>>q;
vector<long long>power(n+q+1,1);
for(int i=1;i<=n+q;++i){
power[i]=power[i-1]*2%MODULUS;
}
long long answer=0;
auto update=[&](int value,bool insert){
vector<int>divisors(1,1);
while(value>1){
int prime=smallest[value],factor=1;
int previousSize=static_cast<int>(divisors.size());
do{
value/=prime;
factor*=prime;
for(int i=0;i<previousSize;++i){
divisors.push_back(divisors[i]*factor);
}
}
while(value>1&&smallest[value]==prime);
}
for(int divisor:divisors){
if(insert){
answer=(answer+phi[divisor]*power[count[divisor]])%MODULUS;
++count[divisor];
}
else{
--count[divisor];
answer=(answer-phi[divisor]*power[count[divisor]])%MODULUS;
if(answer<0){
answer+=MODULUS;
}
}
}
};
for(int i=0;i<n;++i){
int value;
cin>>value;
update(value,true);
}
cout<<answer<<'\n';
while(q--){
int type,value;
cin>>type>>value;
update(value,type==1);
cout<<answer<<'\n';
}
}