Abundant-or-Perfect Range Queries
National Olympiad — National round (2022 season)
Submission name: izobilni.cpp
Problem summary
Count numbers in each inclusive interval whose proper-divisor sum is at least the number itself.
Input
Q and Q pairs l r.
Output
One count per query.
Constraints
1≤Q≤100000; 1≤l≤r≤1000000.
Worked example
Input and output for the worked example discussed below.
Input
3 1 10 2 7 10 50
Output
1 1 10
Solution analysis
- Sieve divisor sums: for each d add it to2d,3d,… . Starting at2d excludes the number itself.
- Build prefix[x]=prefix[x−1]+[sum[x]≥x]. Answer each interval by prefix[r]−prefix[l−1], avoiding repeated divisor work.
- Up to10 only6 qualifies since1+2+3=6. The non-strict source definition includes perfect numbers, so both first sample intervals return1.
Why it works
Each proper divisor visits a multiple exactly once. The sieve sums are therefore exact, and prefix subtraction counts qualifying numbers in each interval.
Complexity: O(MlogM+Q) time and O(M) space for M=10^6; O(1) per query.
Watch out. Use≥ rather than>;1 has proper-divisor sum zero and does not qualify.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
// Each proper divisor visits a multiple exactly once.
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
const int limit=1000000;
vector<int>sum(limit+1,0);
for(int d=1;d*2<=limit;d++){
for(int x=d*2;x<=limit;x+=d){
sum[x]+=d;
}
}
vector<int>prefix(limit+1,0);
for(int x=1;x<=limit;x++){
prefix[x]=prefix[x-1]+(sum[x]>=x);
}
int q;
cin>>q;
while(q--){
int l,r;
cin>>l>>r;
cout<<prefix[r]-prefix[l-1]<<'\n';
}
}