The Missing Factor in a Modular Factorial
National Olympiad — National round (2015 season)
Submission name: multiplier.cpp
Problem summary
A product of 1…N was computed modulo M while omitting exactly one factor. Given remainder R, find every possible omitted factor.
Source clarification. The second official example’s explanatory text has a typographical intermediate product when 3 is omitted. The correct product is 40; the stated remainder 10 and sample output 1 2 4 are correct.
Input
N M R.
Output
All possible omitted factors in increasing order, separated by spaces.
Constraints
2 ≤ N ≤ 30000; 2 ≤ M ≤ 100000; 0 ≤ R < M; input describes an omitted-factor computation.
Worked example
Input and output for the worked example discussed below.
Input
5 15 0
Output
1 2 4
Solution analysis
- Do not divide N! modulo M by a candidate. The modulus may be composite and a factor may have no inverse. Precompute prefix and suffix products modulo M instead.
- For candidate i, prefix[i−1]×suffix[i+1] is the product of all other factors. Test this remainder against R in constant time per candidate, with 64-bit intermediate multiplication.
- For N=5,M=15, omitting 1,2,4 gives remainder zero. Omitting 3 leaves 40 with remainder 10, and omitting 5 leaves 24 with remainder 9. Thus R=0 permits 1 2 4.
Why it works
The two stored product ranges include every factor except i exactly once. Modular multiplication preserves the remainder, so equality with R is necessary and sufficient. Ascending enumeration provides the required order.
Watch out. Modular division is invalid without an inverse. Multiply residues as long long, and avoid a trailing output space. The original explanatory product for omitting 3 has a typo.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int count;
long long modulus;
long long wanted;
cin>>count>>modulus>>wanted;
vector<long long>prefix(count+2,1);
vector<long long>suffix(count+2,1);
for(int value=1;value<=count;value++){
prefix[value]=prefix[value-1]*value%modulus;
}
for(int value=count;value>=1;value--){
suffix[value]=suffix[value+1]*value%modulus;
}
bool first=true;
for(int missing=1;missing<=count;missing++){
// Multiplying disjoint ranges avoids modular division entirely.
if(prefix[missing-1]*suffix[missing+1]%modulus==wanted){
if(!first){
cout<<' ';
}
first=false;
cout<<missing;
}
}
cout<<'\n';
}