デュードニー数 [パソコン甲子園2018 予選 E]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0384

考察過程

1. 点数に比べて問題設定が難しい
2. とりあえず全探索対象を探そう
3. y+aを全探索すれば、10^4が最大なので、全探索できるっぽい

解法

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0384/judge/3162153/C++14

y+aを全探索しよう。
y+aをN乗して、xを作る。
xの各桁を足してyを作る。
あとは、y+Aがy+aになるかをチェックして、なれば、カウントする。
y+aの上限を10^4で固定にすると、Nが大きいとオーバーフローの可能性がでてくるので、
long longで保持するようにして、Mを超えたら即終了するようにする。

int A, N, M;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> N >> M;

    int ans = 0;
    rep(ya, 1, 10101) {
        ll x = 1;
        rep(i, 0, N) x *= ya;
        if (M < x) break;

        int y = 0;
        while (x) {
            y += x % 10;
            x /= 10;
        }

        if (y + A == ya) ans++;
    }
    cout << ans << endl;
}