問題文
定理：二桁以上の正整数であれば、その一の位を取り除いて、残った数を前記一の位の数字の五倍で割ったら、残りの数が17の倍数の場合かつその場合に限って、元の数も17の倍数である。
例えば、34が17の場合である。なぜなら、3-20=-17が17の倍数である。201は17の倍数ではない。なぜなら、20-5=15は17の倍数ではない。一個正整数nを入力して、あなたの任務はこれが17の倍数であるかを判断することだ。
入力フォーマット
入力ファイルは最多で10セットのテストデータを有する。一セットのテストデータは一行を占める。その行は一個の整数n(1<=n<=10^100)のみがあり、判断待ちの正整数を表す。n=0であれば、終了を意味し、この行を処理すべきではない。
出力フォーマット
一セットのテストデータに対して一行を出力して、相応のnが17の倍数であるかを表す。1が肯定を表し、0が否定を表す。
入力サンプル
34
201
2098765413
1717171717171717171717171717171717171717171717171718
0出力サンプル
1
0
1
0分析
この問題の難点は、nの範囲にある。64-bitの整数型を使っても、表示範囲が最大で20桁の十進数くらいになる。100桁まで昇るnとしても使えない。つまり、プログラミング言語のビルトイン型では、nを表現できない。したがって、nを表現できる型またはそれに類するものを作らないといけない。
また、前記定理によると、nが17の倍数であるかは、nより一桁小さい別の整数で判定できる。
つまり、$n=n_0$が17の倍数という問題が下記の問題に相当する。
・$n_1$が17の倍数であるか、さらに次の問題に相当する。
・$n_2$が17の倍数であるか、さらに次の問題に相当する。
・$n_3$が17の倍数であるか、さらに次の問題に相当する。
・……
そして、$n_1 > 10 n_2 > 10^2 n_3 > 10^3 n_4 > ……$
すると、ある$n_p$がプログラミング言語のビルトイン型で表現できる大きさになったら、通常の割り算で17の倍数であるかは判定できるようになる。
前記の定理の中に、掛け算と引き算がある。掛け算に参加する数字は小さく、引き算に参加する数字が大きい。このため、大きい数字の引き算を実装する必要があることになる。
回答案
use std::io;
fn main() {
let mut line = String::new();
while io::stdin().read_line(&mut line).unwrap_or(0) > 0 {
line = String::from(line.trim());
if line == "0" {
break;
}
let bn = BigNumber { digits: line.clone() };
println!("{}", if is_divisible_by_17(&bn) { 1 } else { 0 });
line.clear()
}
}
struct BigNumber {
digits: String
}
impl BigNumber {
fn is_negative(&self) -> bool {
if let Some(first_char) = self.digits.chars().next() {
match first_char {
'-' => true,
_ => false
}
}
else {
false
}
}
fn subtract(&self, other: &BigNumber) -> BigNumber {
let mut result_digits = String::new();
let mut ards : Vec<i8> = Vec::new();
let mut brds : Vec<i8> = Vec::new();
for c in self.digits.chars().rev() {
match c {
'0'..='9' => ards.push((c as u8 - '0' as u8) as i8),
_ => panic!("Only unsigned numbers are allowed in minuend")
}
}
for c in other.digits.chars().rev() {
match c {
'0'..='9' => brds.push((c as u8 - '0' as u8) as i8),
_ => panic!("Only unsigned numbers are allowed in subtrahend")
}
}
let mut diffds : Vec<i8> = Vec::new();
let mut carry : i8 = 0;
let maxlen = if ards.len() > brds.len() {ards.len()} else {brds.len()};
for di in 0..maxlen {
let mut df =
if di >= ards.len() {0} else {ards[di]}
- if di >= brds.len() {0} else {brds[di]}
- carry;
if df < 0 {
carry = 1;
df += 10;
}
else {
carry = 0;
}
diffds.push(df);
}
if carry == 1 {
// The result is negative, and need be complemented.
for d in diffds.iter_mut() {
*d = 9 - *d + carry;
if *d < 10 {
carry = 0;
}
else {
*d -= 10;
}
}
result_digits.push('-');
}
for d in diffds.iter().rev() {
result_digits.push(('0' as u8 + *d as u8) as char);
}
BigNumber {
digits: result_digits
}
}
fn last_digit(&self) -> Option<i8> {
if let Some(c) = self.digits.chars().rev().next() {
Some((c as u32 - '0' as u32) as i8)
}
else {
None
}
}
fn remove_last_digit(&mut self) {
if self.is_negative() {
if self.digits.len() > 2 {
self.digits.pop();
}
else {
self.digits.clear();
self.digits.push('0');
}
}
else {
if self.digits.len() > 1 {
self.digits.pop();
}
else {
self.digits.clear();
self.digits.push('0');
}
}
}
}
fn is_divisible_by_17(number: &BigNumber) -> bool {
if number.digits.len() < 4 {
let intval = number.digits.parse::<i32>().unwrap();
return intval % 17 == 0;
}
let last_digit_times_5: u32 = number.last_digit().unwrap() as u32 * 5;
let mut shortened = BigNumber {digits: number.digits.clone()};
shortened.remove_last_digit();
let subtrahend = BigNumber {digits: last_digit_times_5.to_string()};
let difference = shortened.subtract(&subtrahend);
return is_divisible_by_17(&difference);
}