当前位置: 代码迷 >> 综合 >> 51nod 2482 小b学进制 二分/或者卡
  详细解决方案

51nod 2482 小b学进制 二分/或者卡

热度:83   发布时间:2024-01-15 06:19:59.0

2482 小b学进制

  1. 2.0 秒
  2.  
  3. 262,144.0 KB
  4.  
  5. 20 分
  6.  
  7. 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进制是肯定行的。

  1. 进制位数暴力到1e6次,存在输出,不存在输出 n-1。
  2. 进制最小为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;}