1010 只包含因⼦2 3 5 的数
题⽬链接：
引⽤知识：
丑数
丑数描述
编辑
把只包含质因⼦2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但7、14不是，因为它们包含质因⼦7。 习惯上我们把1当做是第⼀个丑数。
前20个丑数为：1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36。
判断⽅法
编辑
⾸先除2，直到不能整除为⽌，然后除5到不能整除为⽌，然后除3直到不能整除为⽌。最终判断剩余的数字是否为1，如果是1则为丑数，否则不是丑数。
K的因⼦中只包含2 3 5。满⾜条件的前10个数是：2,3,4,5,6,8,9,10,12,15。 所有这样的K组成了⼀个序列S，现在给出⼀个数n，求S中 >= 给定数的最⼩的数。 例如：n = 13，S中 >= 13的最⼩的数是15，所以输出15。 输⼊
第1⾏：⼀个数T，表⽰后⾯⽤作输⼊测试的数的数量。（1 <= T <= 10000) 第2 - T + 1⾏：每⾏1个数N(1 <= N <= 10^18)
输出
共T⾏，每⾏1个数，输出>= n的最⼩的只包含因⼦2 3 5的数。
输⼊样例
5
1
8
13
35
77
输出样例
2
8
15
36
80
解题思路：丑数打表+⼆分查。如果去枚举的话，抱歉time limittted 下⾯是我的代码纪新刚
#include "bits/stdc++.h"
using namespace std;
#define LL long long
LL a[100000];
LL ugly(LL n)
{
while(n>=2&&n%2==0){
n/=2;
}
while(n>=5&&n%5==0){
n/=5;
}
while(n>=3&&n%3==0){
n/=3;
}
if(n==1) return 1;
else return 0;
}
LL min1(LL a,LL b,LL c)
{
LL c1=min(a,b);
LL d=min(c1,c);
第一看点
return d;
}
int bsearch(LL a[], int n,LL key){
int low = 0;
int high = n;
int mid = 0;
while(low <= high) {
mid = low + ((high-low) >> 1);
if(key <= a[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return low <= n ? low : -1;
}
int main(int argc, char const *argv[]) {
实践理性批判
int t;
int n=1;
cin>>t;
a[1]=1;
电力监测
int p2,p3,p4;
p2=p3=p4=1;经济增长
while(n<11000)
{
a[++n]=min1(2*a[p2],3*a[p3],5*a[p4]);
if(a[n]==2*a[p2]) p2++;
if(a[n]==3*a[p3]) p3++;
if(a[n]==5*a[p4]) p4++;
}
// cout<<a[11000]<<endl; // for(int i=1;i<10;i++)
// cout<<a[i]<<" "<<endl; for(int i=0;i<t;i++)
{
LL n2;
cin>>n2;
// cout<<n2<<endl;
if(n2==1) printf("2\n"); else{
int x=bsearch(a,n,n2); // cout<<x<<endl;
cout<<a[x]<<endl;
}
}多工位冲压机械手
return 0;
}
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议