SRM473 Div2 Hard(1000) ChildlessNumbers

ChildlessNumbers

kを整数として、X=kYとなるXのみ調べる。
Y = kY/D(kY)
⇔ k = D(kY) ≦ 9 log₁₀kY = 9 log₁₀k + 9 log₁₀Y
なので、k<200 程度で充分。

class ChildlessNumbers
{
    int D( long long n );
public:
    int howMany( int A, int B );
};

int ChildlessNumbers::D( long long n )
{
    int r = 0;
    while ( n > 0 )
        r += n % 10,
        n /= 10;
    return r;
}

int ChildlessNumbers::howMany( int A, int B )
{
    int c = 0;

    for ( int Y=A; Y<=B; Y++ )
    {
        bool f = true;
        for ( long long k=1; f && k<200; k++ )
            if ( k*Y/D(k*Y) == Y )
                f = false;
        if ( f )
            c++;
    }

    return c;
}