[AOJ] No. 0384 デュードニー数

2019年12月19日

問題

方針

各桁の和の最大値は最大でも \( 72 \) なので、\( y \) を決め打ちして考えます。条件を満たす \( y \) について、\( x \) の桁和が \( y \) になるかどうかを調べます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll my_pow(ll x, ll n) {
    if (n == 0) return 1;
    if (n % 2 == 0) return my_pow(x * x, n / 2);
    return x * my_pow(x, n - 1);
}

int main() {
    ll a, n ,m;
    cin >> a >> n >> m;
    string s = to_string(m);
    ll t = (s.length() - 1) * 9 + s[0] - '0' - 1;
    if (s[0] == '9') t++;
    int ans = 0;
    
    for (ll i = 1; i <= t; i++) {
        ll x = my_pow(i + a, n);
        if (x > m) break;
        string k = to_string(x);
        ll d = 0;
        for (int j = 0; j < k.length(); j++) {
            d += k[j] - '0';
        }
        if (d == i) ans++;
    }
    cout << ans << "\n";
    return 0;
}