Sum of Common Multiples in an Interval
National Olympiad — National round (2012 season)
Submission name: sum.cpp
Problem summary
Find the sum of all integers in [A,B] divisible by both P and Q.
Input
A B P Q.
Output
The sum, or 0 if there is no qualifying integer.
Constraints
0 < A < B ≤ 10^9; 2 < P,Q < 100.
Worked example
Input and output for the worked example discussed below.
Input
3 50 6 4
Output
120
Solution analysis
- Being divisible by both P and Q is equivalent to being a multiple of L=lcm(P,Q)=P/gcd(P,Q)×Q. Do not use P×Q when the two inputs share a factor.
- The multipliers range from first=ceil(A/L) to last=floor(B/L). If first>last the answer is zero; otherwise sum this consecutive integer range and multiply by L.
- For P=6 and Q=4, L=12. The interval [3,50] contains 12,24,36,48, whose sum is 120. Formula L×(first+last)×count/2 produces the same result without looping.
Why it works
The common multiples are precisely L times each integer multiplier in the derived interval. The arithmetic-progression formula sums those and only those values.
Complexity: O(log min(P,Q)) time for gcd and O(1) extra space; all subsequent operations are constant time.
Watch out. Use 64-bit arithmetic throughout. Divide out the gcd before multiplying, and include both interval endpoints.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<numeric>
using namespace std;
int main(){
long long left;
long long right;
long long p;
long long q;
cin>>left>>right>>p>>q;
long long multiple=p/gcd(p,q)*q;
long long first=(left+multiple-1)/multiple;
long long last=right/multiple;
long long answer=0;
if(first<=last){
// The multiplier range is an ordinary arithmetic progression.
answer=multiple*(first+last)*(last-first+1)/2;
}
cout<<answer<<'\n';
}