SRM484 Div1 Easy(250), Div2 Medium(550) RabbitNumber

RabbitNumber

S(n+m)≦S(n)+S(m)。等号成立はn+mの計算で繰り上がりが発生しないとき。x=Σd_i10ⁱとすると、S(x)*S(x)=Σ_iΣ_jd_id_j。筆算を考えれば、繰り上がりが発生しないときS(x*x)=S(x)*S(x)。その必要条件は任意のiについてd_i≦3。

int next( int n )
{
    n++;
    int b = 1;
    while ( n/b%10 >= 4 )
        n = n/b/10*b*10 + b*10,
        b *= 10;
    return n;
}

int S( long long n )
{
    int c = 0;
    while ( n > 0 )
        c += n % 10,
        n /= 10;
    return c;
}

class RabbitNumber{public:
int theCount( int low, int high )
{
    int c = 0;
    for ( int x=low; x<=high; x=next(x) )
        if ( S((long long)x*x) == S(x)*S(x) )
            c++;
    return c;   
}};