A19849. 好数
填空题
容易
知识点
题目描述
好数
题目描述
小明特别喜欢数字3，他认为如果一个正整数等于3的若干个整数次幂相加，并且这些整数次幂均不重复出现，这样的数是“好数”。例如：
1是好数，1=3^0
4是好数，4=3^1+3^0
12是好数，12=3^2+3^1
2不是好数，2=3^0+3^0，3^0出现了2次
15不是好数，15=3^2+3^1+3^1，3^1出现了2次
20不是好数，20=3^2+3^2+3^0+3^0，3^2和3^0各出现2次
虽然15和20还有其他3整数次幂写法，比如15=3^1+3^1+3^1+3^1+3^1，但仍不满足好数定义。
现在输入一个正整数n，输出不小于n的所有好数中最小的一个。
输入格式
仅一行，正整数n。（1<=n<=10^5）。
输出格式
一个正整数，表示不小于n的所有好数中最小的一个。
输入样例1
14输出样例1
27输入样例2
13输出样例2
13输入样例3
100000输出样例3
177147提示
样例1说明：14至26之间的整数都不是好数，因此不小于14的好数中最小的是27；
样例2说明：13=3^2+3^1+3^0，因此不小于13的好数中最小的就是13；
样例3说明：177147=3^11。
参考答案
参考1：
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char *argv[])
{
long long n,m=1,ans=0;
scanf("%lld",&n);
while(ans<n){//升幂累加
ans+=m;
m*=3;
}
while(m){//降幂试减
if(ans-m>=n) ans-=m;
m/=3;
}
printf("%d\n",ans);
return 0;
}
参考2：
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char *argv[])
{
long long n,i;
scanf("%lld",&n);
while(1){
bool b=true;
i=n;
while(i){
if(i%3==2) {b=false;break;}
i=i/3;
}
if(b) break;
else n++;
}
printf("%d\n",n);
return 0;
}
上一题
下一题