SRM484 Div1 Easy RabbitNumber

2015/04/14 (Tue) srm OEIS 数学

問題

問題文

正の整数 $x$ に対し $ S(x) $ を 10 進数表記したときの桁の和と定義する。 $[low,high]$ に $ S(x \times x) = S(x) \times S(x) $ を満たす整数 $x$ はいくつあるか。

方針

$x$ の全ての桁が $0,1,2,3$ に含まれていることが必要条件です。 そのような数について条件を満たすものを全探索で数えます。

僕が実際に解いたときは、全く分からなかったので取り敢えず全探索してみたところ上のような特徴が見え、 出したら通ってしまいました。 証明は kusano さんの記事 がわかりやすいです。

OEIS に載ってたりもします。

実装

class RabbitNumber{
public:
    int theCount( int low, int high ){
        int ans = 0;
        rep(i,4LL*4*4*4*4 * 4*4*4*4*4){
            ll x = 0;
            ll t = i;
            rep(j,10){
                x = x*10 + t%4;
                t /= 4;
            }
            if(S(x*x) == S(x)*S(x) && low <= x && x <= high){
                ans++;
            }
        }
        return ans;
    }
    int S(ll x){
        int res = 0;
        while(x){
            res += x%10;
            x/=10;
        }
        return res;
    }
};