4進FizzBuzz [yukicoder No.593]

https://yukicoder.me/problems/no/593

解法

https://yukicoder.me/submissions/215784

4進数を10進数に直す方法を知らないと解くのは難しい。
下からi桁目の値に対して×4^iをして総和を取ると10進数に変換できる。
しかし、桁数から見ると、10進数にそのまま変換すると値が大きすぎるので無理。
　
ここで、「4進数の数Nが3の倍数である」ということを「4進数の数Nを3を法として剰余を取ると0である」と言い換える。
他の倍数も同様に言い換えることができるため、剰余を取りながら10進数に変換していくことにする。
　
そのために、get関数を作る。
get(mod) := 4進数の数Nを10進数にmodを法として変換したときの値
下の桁から順に変換していけばいい。
下からi桁目の値は×4^iをするが、その次のi+1桁目は×4^(i+1)なので、書ける部分をxとして分けておき、4倍しながら使いまわす。

string N;
//---------------------------------------------------------------------------------------------------
int get(int mod) {
    int x = 1;

    int res = 0;
    int n = N.length();
    rrep(i, n - 1, 0) {
        res = (res + (N[i] - '0') * x) % mod;
        x = (x * 4) % mod;
    }
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    if (get(15) == 0) printf("FizzBuzz\n");
    else if (get(3) == 0) printf("Fizz\n");
    else if (get(5) == 0) printf("Buzz\n");
    else printf("%s\n", N.c_str());
}