Repeated Last-Three-Digit Squaring
National Olympiad — Municipal round (2020 season)
Submission name: mul.cpp
Problem summary
Repeat N times: square A and replace it by the integer formed by the last three decimal digits of the square. Print the final value without leading zeros.
Input
Two integers A and N.
Output
The final value of A.
Constraints
0 < A,N < 1000.
Worked example
An independently prepared example for this explanation.
Input
77 3
Output
681
Solution analysis
- The last three digits of a nonnegative integer are its remainder modulo 1000. Therefore one step is A = (A·A) mod 1000.
- Perform exactly N updates, always squaring the value produced by the previous update. Every stored value stays between 0 and 999.
- For 77, the first square is 5929, giving 929. The next square gives remainder 41, and 41² gives remainder 681. A remainder such as 041 is stored and printed as the integer 41.
Why it works
The remainder modulo 1000 is exactly the value of the final three digits. Applying this operation once per iteration therefore reproduces every prescribed step, including the final one.
Complexity: O(N) time and O(1) extra space.
Watch out. This repeatedly squares; it is not A raised to N. Do not pad the output with zeros.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
int value, steps;
cin >> value >> steps;
for (int step = 0; step < steps; step++) {
// Modulo 1000 keeps precisely the final three digits.
value = value * value % 1000;
}
cout << value << '\n';
}