Smallest Consistent Bouquet Delivery
National Olympiad — National round (2009 season)
Submission name: bouquet.cpp
Problem summary
Find the smallest positive rose count leaving remainder1 for four bouquet sizes and remainder0 for a fifth size p.
Source clarification. The source defines no output convention for inconsistent congruences, although its printed bounds permit them. A solution exists exactly when gcd(lcm(n,m,k,l),p)=1. Otherwise the program writes a diagnostic to stderr and no invented stdout answer. Solvable answers use exact decimal arithmetic.
Input
n m k l, then p.
Output
The exact minimum rose count; the original specifies no impossible-case output.
Constraints
1 < n,m,k,l,p <10000. Solvability requires gcd(lcm(n,m,k,l),p)=1.
Worked example
Input and output for the worked example discussed below.
Input
3 4 5 6 7
Output
301
Solution analysis
- Let L be the least common multiple of the first four sizes. Their conditions are equivalent to roses=L×t+1. The final condition is L×t≡−1 modulo p.
- This congruence is solvable precisely when gcd(L,p)=1. Then inspect t=1,2,… until the congruence holds; its least solution is below p. In the sample L=60,t=5, giving301.
- L fits signed64 bits, but L×t+1 may not. Multiply the decimal string for L by t with carry initialized to1. For inconsistent inputs the program reports to stderr instead of inventing an unspecified stdout answer.
Why it works
The LCM criterion is equivalent to all four remainder-one requirements. The linear-congruence criterion proves existence, and increasing t finds the least feasible value. Exact decimal multiplication prevents overflow in the resulting count.
Watch out. Divide before multiplying for lcm. Do not form the final product in long long or assume the printed bounds guarantee a solution.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<numeric>
#include<string>
using namespace std;
int main(){
long long common=1;
for(int i=0;i<4;i++){
long long size;
cin>>size;
common=common/gcd(common,size)*size;
}
long long p;
cin>>p;
if(gcd(common,p)!=1){
cerr<<"The bouquet requirements are inconsistent.\n";
return 0;
}
long long multiplier=1;
while((multiplier*(common%p)+1)%p!=0){
multiplier++;
}
string answer=to_string(common);
long long carry=1;
// Exact decimal multiplication also adds the one leftover rose.
for(int i=int(answer.size())-1;i>=0;i--){
long long value=(answer[i]-'0')*multiplier+carry;
answer[i]=char('0'+value%10);
carry=value/10;
}
while(carry>0){
answer.insert(answer.begin(),char('0'+carry%10));
carry/=10;
}
cout<<answer<<'\n';
}