AT2038

Purslane · 2022-06-29 09:48:36 · 题解

Solution

数学题 .

我们不妨设 n=a_0+a_1b+a_2b^2+a_3b^3+ \cdots , 则 s=a_0+a_1+a_2+\cdots .

先考虑特殊情况 :

然后 , 我们用 n 减去 s 得到 :

我们很容易知道 , b^n-1=(b-1)(b^{n-1}+b^{n-2}+\cdots+1) . 所以说 , 右式可以提出 (b-1) . 那么很显然 , (b-1)|(n-s) . 那么 , b 可能取值的数量就缩成了 \sqrt{n} 的量级 . 然后直接套用函数 , 逐个判断可能的 b 就可以了 .

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
int n,s;
int f(int b,int n) {
    if(n<b) return n;
    return f(b,n/b)+(n%b);
}
int check(int b) {
    if(f(b,n)==s) return 1;
    return 0;
}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>s;
    if(n<s) {cout<<-1;return 0;}
    if(n==s) {cout<<n+1;return 0;}
    int d=n-s,ans=LONG_LONG_MAX;
    ffor(i,1,sqrt(d)) if(d%i==0) {
        if(check(i+1)) ans=min(ans,i+1);
        if(check(d/i+1)) ans=min(ans,d/i+1);
    }
    if(ans==LONG_LONG_MAX) {cout<<-1;return 0;}
    cout<<ans;
    return 0;
}