Problem 20 "Factorial digit sum"

n! means n × (n − 1) × ... × 3 × 2 × 1

For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

問 20 「各位の数字の和 2」

n! は n × (n − 1) × ... × 3 × 2 × 1

例えば, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800 となる.

この数の各桁の合計は 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 である.

では, 100! の各位の数字の和を求めよ.

struct BigNum {
    v: Vec<u64>,
}

impl BigNum {
    const TEN_MIL: u64 = 10_000_000_000;
    fn factorial(&mut self) {
        assert!(self.v.len() == 1);
        let up = self.v[0];
        assert!(((u64::MAX as f32 - Self::TEN_MIL as f32) / Self::TEN_MIL as f32) > (up as f32));
        for b in 2..up {
            self._multiply(b);
        }
    }
    fn _multiply(&mut self, b: u64) {
        let mut carry = 0u64;
        for con in self.v.iter_mut() {
            *con *= b;
            *con += carry;
            if *con < Self::TEN_MIL {
                carry = 0;
                continue;
            }
            carry = *con / Self::TEN_MIL;
            *con -= carry * Self::TEN_MIL;
        }
        if carry != 0 {
            self.v.push(carry);
        }
    }
    fn sum_of_digits(&self) -> u32 {
        let mut sum = 0u32;
        for &con in &self.v {
            let mut t = con;
            while t > 0 {
                sum += (t % 10) as u32;
                t /= 10;
            }
        }
        sum
    }
}

fn main() {
    let mut a = BigNum { v: vec![100u64] };
    a.factorial();
    let sum = a.sum_of_digits();

    println!("{}", sum);
    assert_eq!(sum, 648);
}