SRM509 Div1 Easy

250

9で割った余りなのが重要。10^nをかけたとしても、あまりに変化がない。
そして、各数字は 2^(文字列の長さ) 回だけ登場する。

小さいケースを手で試していたら気がついた。
簡単だとも思わないけど、Editorials を見る限りでは正答率が低いわけではない。
こういう類を苦手に思わない人たちってのはどういう過程を経て答えに行き着くのか・・・。

class LuckyRemainder {
public:
  int getLuckyRemainder(string X)
  {
    lli sum = accumulate(X.begin(), X.end(), 0LL) - (lli)('0' * X.size());
    sum = sum << (X.size() - 1);
    return sum % 9LL;
  }
};