ABC044 D - 桁和

問題

自然数 を 進数で表したときの桁和を とするとき、 を満たす最小の を求めよ。

問題リンク：ABC044 D

制約

• 
• 

解法

条件をまとめると、

• 
• 

となるような を探せばよい。

ここで2つの式の差をとると、

となる。 は必ず を因数に持つことから右辺は で割り切れる。すなわち、

が成り立つことが導かれる。よって解の候補は の約数+1。

以上から、 の全ての約数 対し を求め と一致するかを確認すれば解が求まる。 の場合は 以外の候補はない。

Code

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

ll f(ll b, ll n){
    if(n<b) return n;
    else return f(b,n/b)+n%b;
}

vector<ll> divisor(ll n) {
    vector<ll> res;
    for (ll i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            res.push_back(i);
            if (i != n / i) res.push_back(n / i);
        }
    }
    return res;
}

int main() {
    ll n, s;
    cin >> n >> s;
    vector<ll> d = divisor(n-s);
    d.push_back(n);
    sort(d.begin(), d.end());
    for(auto x : d){
        if(f(x+1,n)==s){
            cout << x+1 << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}