Divisibility of a Very Long Integer
National Olympiad — Municipal round (2011 season)
Submission name: div.cpp
Problem summary
Determine whether a positive decimal integer is divisible by 2, by 3 and by 5, even when it has thousands of digits.
Input
One positive decimal integer n, supplied as a string.
Output
Three 0/1 indicators for divisibility by 2, 3 and 5 in that order.
Constraints
At most 2011 decimal digits.
Worked example
Input and output for the worked example discussed below.
Input
12
Output
1 1 0
Solution analysis
- A number is divisible by 2 exactly when its last digit is even, and divisible by 5 exactly when its last digit is 0 or 5. Only divisibility by 3 needs the other digits.
- The decimal place values 1,10,100,… are all congruent to 1 modulo 3. Therefore the whole number has the same remainder modulo 3 as its digit sum.
- For 12, the last digit 2 is even, the digit sum 3 is divisible by 3, and the last digit is neither 0 nor 5. The indicators are 1 1 0. For 123451234512345, the result is 0 1 1. No big-integer conversion is necessary.
Why it works
The standard last-digit tests follow from 10 being a multiple of 2 and 5. The digit-sum test follows by reducing the decimal expansion modulo 3. Applying these exact equivalences yields all three required indicators.
Watch out. Do not parse the input as long long or use floating-point arithmetic. Output all three indicators in the specified order, separated by spaces.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<limits>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<vector>
using namespace std;
int main(){
string number;
cin>>number;
int sum=0;
for(char digit:number){
// Decimal digits have the same contribution modulo three.
sum+=digit-'0';
}
int last=number.back()-'0';
cout<<(last%2==0)<<' '<<(sum%3==0)<<' '<<(last%5==0)<<'\n';
}