SRM509 Div1 Easy(250), Div2 Medium(500) LuckyRemainder

LuckyRemainder

整数xを9で割った余りは、xの各桁の和を9で割った余りに等しい。Xの桁数をnとすると、全ての桁は2^n-1回足される。

#include <string>
using namespace std;

class LuckyRemainder{public:
int getLuckyRemainder( string X )
{
    int n = (int)X.length();
    long long s = 0;
    for ( int i=0; i<n; i++ )
        s += X[i]-'0';
    return s*(1ll<<(n-1))%9;
}};