Last Digit after Removing Factors
National Olympiad — National round (2019 season)
Submission name: last.cpp
Problem summary
From the factors 1,2,…,n, remove all even factors and all factors divisible by 5. Find the last digit of the product of the remaining factors. Answer for three supplied values of n.
Input
Three positive integers k, l, and m.
Output
Three lines: the last product digit for k, then l, then m.
Constraints
1 ≤ each supplied value ≤ 1000000000000000000.
Worked example
An independently prepared example for this explanation.
Input
1 2 3
Output
1 1 3
Solution analysis
- Only factors whose last digits are 1,3,7,9 remain. In every complete block of ten consecutive integers, their last digits multiply to 1·3·7·9, which is 9 modulo 10.
- If n=10q+r, the complete blocks contribute 9^q modulo 10. This is 1 when q is even and 9 when q is odd. Multiply by the allowed last digits from 1 through r for the incomplete block.
- For n=22, two complete blocks contribute 9²≡1. The remaining factors through 22 contribute only the last digit 1 from 21, so the answer is 1. For n=13, one block contributes 9, then 11 and 13 contribute 1 and 3, giving 7 modulo 10.
Why it works
All factors divisible by 2 or 5 are removed, leaving exactly the four listed residue classes. Last digits of a product depend only on factor residues modulo ten. Multiplying the complete-block contribution and the remaining residues therefore gives the exact last digit.
Watch out. Do not compute the factorial or iterate up to n. There are exactly three answers, each on its own line.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int lastDigit(long long n) {
long long blocks = n / 10;
// Each complete block contributes 1*3*7*9 = 9 modulo ten.
int answer = blocks % 2 == 0 ? 1 : 9;
int remainder = static_cast<int>(n % 10);
for (int digit = 1; digit <= remainder; ++digit) {
if (digit % 2 != 0 && digit % 5 != 0) {
answer = answer * digit % 10;
}
}
return answer;
}
int main() {
for (int query = 0; query < 3; ++query) {
long long n;
cin >> n;
cout << lastDigit(n) << '\n';
}
}