2482 小b学进制
- 2.0 秒
- 262,144.0 KB
- 20 分
- 3级题
小b最近在学习进制转化。
对于一个10进制整数n和一个数k,她能快速求出k进制下的n。
如果k进制下的n所有数位都是1,即形如11111111,那么小b就会觉得开心。
现在给定n,请你求出最小的k使得k进制下的n能让小b开心。
收起
输入
输入一个十进制整数,表示n(没有前导0),其中3≤n≤10^18
输出
输出一个整数,表示最小的k
输入样例
4681
输出样例
8
分析:
n-1进制是肯定行的。
- 进制位数暴力到1e6次,存在输出,不存在输出 n-1。
- 进制最小为2,长度最多为64,我们知道在长度确定下,进制越大数值越大,满足单调性,二分即可。但坑点在于中间的数可能存不小,需要用long double
二分
#include <bits/stdc++.h>
using namespace std;
const int N=1e18;
typedef long long LL;
typedef long double ll;
LL n;
int check(LL mid,int len)
{ll pw=1, sum=0;for(int i=1; i<=len; i++){sum+=pw;if(sum>n) return 0;pw*=mid;}if(sum==n) return 1;return -1;}
int main()
{scanf("%lld",&n);LL minn=n-1,ans=n-1; for(int i=1; i<=64; i++){LL l=2,r=n;while(l<r){LL mid=(l+r)>>1;//cout<<mid<<endl;int temp=check(mid,i);if(temp>=0){if(temp==1){minn=min(ans,mid);}r=mid;}elsel=mid+1;}ans=min(minn,ans);}cout<<ans<<endl;}
#include <bits/stdc++.h>
using namespace std;
const int N=1e18;
typedef long long LL;
int main()
{LL n;scanf("%lld",&n);for(LL i=2;i<=1e6; i++){LL sum=0;LL base=1;if(n%i!=1){continue;}for(LL j=1;; j++){sum+=base;//cout<<sum<<" "<<i<<endl;if(sum==n){printf("%d\n",i);return 0;}if(sum>n)break;base*=i;}}cout<<n-1<<endl;}