Equal Consecutive Sums
National Olympiad — National round
Submission name: cosums.cpp
Problem summary
For each given positive b, count positive integer pairs (a,c) such that the first a terms of c,c+1,…,c+a+b−1 have the same sum as the following b terms.
Input
Number of queries, then one b per query.
Output
One count per query, modulo 100,000,007.
Constraints
At most 10 queries; 0 < b < 100,000,000.
Worked example
An independently prepared example for this explanation.
Input
2 1 2
Output
1 1
Solution analysis
- The earlier terms are smaller, so a>b. Put d=a−b. Expanding the two arithmetic sums gives 2dc=2b²−d²+d.
- Thus d divides 2b². Factor b, double its prime exponents and add one exponent of 2, enumerate the divisors d, and count those for which 2b²/d−d+1 is positive and even.
Why it works
Every solution gives a positive divisor d and the displayed integer c. Conversely each accepted divisor uniquely determines positive c and a=b+d satisfying the original equality, giving a bijection.
Complexity: O(√b+τ(2b²)) time and O(τ(2b²)) space per query.
Watch out. The modulus is 10⁸+7, not 10⁹+7. Use 64-bit arithmetic.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every solution gives a positive divisor d and the displayed integer c. Conversely each
// accepted divisor uniquely determines positive c and a=b+d satisfying the original equality, giving a
// bijection.
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main(){
int q;
cin>>q;
while(q--){
long long b;
cin>>b;
long long x=b;
map<long long,int>f;
for(long long p=2;p*p<=x;p++){
while(x%p==0){
f[p]+=2;
x/=p;
}
}
if(x>1){
f[x]+=2;
}
f[2]++;
vector<long long>d{1};
for(auto[p,e]:f){
int old=d.size();
long long power=1;
for(int k=1;k<=e;k++){
power*=p;
for(int i=0;i<old;i++){
d.push_back(d[i]*power);
}
}
}
long long t=2*b*b,ans=0;
for(long long v:d){
long long twiceC=t/v-v+1;
if(twiceC>0&&twiceC%2==0){
ans++;
}
}
cout<<ans%100000007<<'\n';
}
}