传送门
数论好题啊。
首先对于b<=sqrt(n)b<=sqrt(n)b<=sqrt(n)的情况直接枚举b判断一下就行了。
下面谈一谈如何解决b>sqrt(n)b>sqrt(n)b>sqrt(n)的情况。
如果b>sqrt(n)b>sqrt(n)b>sqrt(n)
显然有：
nnn modmodmod bbb +++ n/b=sn/b=sn/b=s
nnn modmodmod bbb +++ b∗(n/b)=sb*(n/b)=sb∗(n/b)=s
这里用的是整除向下取整
我们不妨令A=nA=nA=n modmodmod bbb,B=n/bB=n/bB=n/b。
于是就有了下面的式子：
A+B=sA+B=sA+B=s
A+b∗B=nA+b*B=nA+b∗B=n
A,B≤sqrt(n)A,B\le sqrt(n)A,B≤sqrt(n)
由头两个式子可以推出
(b−1)∗B=n−s(b-1)*B=n-s(b−1)∗B=n−s
于是枚举b−1b-1b−1就可以了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,s,len;
inline bool check(ll x,ll tmp){
if(tmp==1)return true;
ll cnt=0;
while(x)cnt+=x%tmp,x/=tmp;
return cnt==s;
}
int main(){
cin>>n>>s,len=(ll)sqrt(n)+1;
for(ll i=2;i<=len;++i)if(check(n,i)){cout<<i;return 0;}
if(n<=s){cout<<(n<s?-1:n+1);return 0;}
ll tmp=n-s,ttmp=tmp/len+1;
for(int i=ttmp;i;--i)if(tmp%i==0&&s>=i&&s-i<=tmp/i&&i<=tmp/i){cout<<tmp/i+1;return 0;}
cout<<-1;
return 0;
}