Range sums of symmetric blocks
National Olympiad — Regional round
Submission name: sequence.cpp
Problem summary
Concatenate the blocks 1; 1,2,1; 1,2,3,2,1; and so on. Answer sums over 1-based position intervals [l,r], modulo 1000000007.
Input
q followed by q pairs l r.
Output
One modular sum per query.
Constraints
1≤q≤100000; 1≤l≤r≤10^12.
Worked example
An independently prepared example for this explanation.
Input
2 1 4 5 9
Output
5 9
Solution analysis
- Block k has length 2k−1 and sum k². The first k blocks end at position k².
- For a prefix ending at x, find k=floor(sqrt(x)). Sum complete blocks using k(k+1)(2k+1)/6.
- The remaining t=x−k² values lie in block k+1. Use an arithmetic-series sum for its ascending part and, if necessary, its descending part. Subtract two prefixes.
Why it works
The square endpoint identity locates the only partial block exactly. Complete-block and partial arithmetic sums partition the prefix without overlap.
Complexity: O(q) arithmetic operations with integer-corrected square roots; O(1) space.
Watch out. Correct floating-point square-root rounding and avoid overflowing intermediate products before taking the modulus.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The square endpoint identity locates the only partial block exactly. Complete-block and
// partial arithmetic sums partition the prefix without overlap.
#include<iostream>
#include<tuple>
#include<cmath>
using namespace std;
using I=__int128_t;
const long long MOD=1000000007;
long long pref(long long x){
if(x<=0){
return 0;
}
long long k=sqrtl(x);
while((k+1)*(k+1)<=x){
++k;
}
while(k*k>x){
--k;
}
long long t=x-k*k,h=k+1;
I ans=I(k)*(k+1)*(2*k+1)/6;
if(t<=h){
ans+=I(t)*(t+1)/2;
}
else{
long long d=t-h;
ans+=I(h)*(h+1)/2+I(d)*(2*h-d-1)/2;
}
return ans%MOD;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin>>q;
while(q--){
long long l,r;
cin>>l>>r;
cout<<(pref(r)-pref(l-1)+MOD)%MOD<<'\n';
}
}