Lottery Winners by Exact Divisibility Count
National Olympiad — National round (2011 season)
Submission name: lottery.cpp
Problem summary
Count integers in [p,q] divisible by exactly k of n distinct given positive divisors.
Input
n and k, the n divisors, then p and q.
Output
The number of qualifying integers.
Constraints
1 ≤ n ≤ 100000; 1 ≤ k ≤ 20; divisors ≤ 10^9; 1 ≤ p ≤ q ≤ 10^9; q−p ≤ 100000.
Worked example
Input and output for the worked example discussed below.
Input
2 1 2 3 1 10
Output
6
Solution analysis
- The absolute endpoints can be large, but the interval is short. Allocate one counter for each number p…q instead of a billion-element array.
- For each divisor d, find its first multiple not below p: ceil(p/d)×d. Visit that multiple, then add d repeatedly until passing q. Increment the corresponding interval counter. Divisors larger than q visit nothing.
- In [1,10], divisors 2 and 3 mark 2,4,6,8,10 and 3,6,9 respectively. Exactly one mark remains on 2,3,4,8,9,10, giving 6. Number 6 gets two marks and must be excluded.
Why it works
A divisor marks exactly its multiples in the requested interval, once each. Hence every counter equals the number of input divisors dividing that integer. Counting counters equal to k implements the condition exactly.
Watch out. Count exactly k, not at least k. First-multiple arithmetic should use long long. Divisors are distinct by contract; duplicates would otherwise count twice.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int count;
int wanted;
cin>>count>>wanted;
vector<long long>divisor(count);
for(long long&value:divisor){
cin>>value;
}
long long left;
long long right;
cin>>left>>right;
vector<int>marks(right-left+1,0);
for(long long value:divisor){
// Start at the first multiple inside the short interval.
long long first=(left+value-1)/value*value;
for(long long multiple=first;multiple<=right;multiple+=value){
marks[multiple-left]++;
}
}
int answer=0;
for(int value:marks){
if(value==wanted){
answer++;
}
}
cout<<answer<<'\n';
}