多倍長整数問題はPythonで

Joeくんが言及してたやつ

yukicoderにC++じゃTLEするのでPython使えって書いてる問題が合った気がするけど思い出せねえ（たしか2進数の入力をintに変換するのとかPythonを使うのがかなり速いはず）
— Joe@社会 (@xuzijian629) 2019年3月14日

yukicoder No.381 名声値を稼ごう Extra

No.381 名声値を稼ごう Extra - yukicoder

言語の特性上C++,Java,C#で正答するのは困難かもしれません。Ruby,Pythonでの回答をおすすめします。

問題を見てもらえば分かる通り、 $N$ を2で割りながら足していったやつと $2N$ との差を求めるだけなんだけど
入力制約が $N\le 10^{1000000}$ なのね

制約のゆるい（Nがlong longに収まる）バージョンもあって

yukicoder No.378 名声値を稼ごう

No.378 名声値を稼ごう - yukicoder
これは簡単（やるだけ、というかやるまでもない）

#include <iostream>
using namespace std;

long long hobby(long long N) {
    long long ans = 0;
    while (N) {
        ans += N;
        N /= 2;
    }
    return ans;
}

long long pro(long long N) {
    return N*2;
}

int main() {
    long long N; cin >> N;
    long long ans = pro(N) - hobby(N);
    cout << ans << endl;
    return 0;
}

1つ工夫できるところがあって
「Nを2で割りながら足す」というのはNの各ビットが0になるまで右シフトしていった合計なので、i番目のビットが立っているとすると求める合計値にそのビットが関与する分は $2^{i+1}-1$ になる。（例：1000→1111 = 1000*2-1）
これを全て足し合わせると $2N-popcount(N)$ になるので、 $2N$ との差は $popcount(N)$ になる。

#include <iostream>
using namespace std;

int main(){
    long long N; cin >> N;
    cout << __builtin_popcountll(N) << endl;
    return 0;
}

→AC

さて。
10進数で100万桁の多倍長整数でこの演算をするには要するに、100万桁の10進表記された文字列を読み込んで2進法（ないし $2^n$ 進法）へと基数変換する実装が必要になる。

こういうのはPythonが断然有利で

N = int(input())
popcount = bin(N).count('1')
print(popcount)

で済んでしまう。1行にまとめて

print(bin(int(input())).count('1'))

とすることも可能だ。
ここでは bin(x).count('1') が（xが多倍長整数であっても）popcountを計算してくれる。
→AC

入力が100万桁でも"Extra"の時間制限8秒をローカルでギリギリ切れた。（ジャッジでは6183msだった）
時間がかかるのは input() を多倍長整数として（内部で $2^{30}$ 進法？に）置き換える部分。
$10^{1000000}$ は2進法で3321929桁*1なので、popcount(N)は最大でも3321928にしかならず、1004535809 での剰余をとる必要はない。