當前位置:網站首頁>G - Ugly Numbers

G - Ugly Numbers

2022-01-27 22:12:55 Five6667

醜數是指不能被2,3,5以外的其他素數整除的數。把醜數從小到大排列起來,結果如下:
1,2,3,4,5,6,8,9,10,12,15……
求第1500個醜數

輸入

沒有輸入

輸出

The 1500'th ugly number is <number>.

這輸出是真坑。 number左右的<>是沒有的;

講講思路吧,暴力肯定行不通了,但是醜數就是 質因子只有,1 ,2 ,3,5 的數 ,但是他可以是 1 2 2 3 5 ,1 2 3 3 5 ,1 2 3 5 5 ,所以我們可以枚舉醜數的個數,我們認為最小的醜數是 1 那麼第二小的就是 1*2 以此類推,1 2 3 5 是一個界 然後 1 2 2 3 5 是稍微大一點的

#include<bits/stdc++.h>
using namespace std;
long long int i,j,k,a[1010010],cnt,n;
int main(){
	n=1500;
	a[1]=1;
	int t2=1,t3=1,t5=1;
	for(i=2;i<=n;i++){
		a[i]=min(a[t2]*2,min(a[t3]*3,a[t5]*5));
		if(a[i]==a[t2]*2) t2++;
		if(a[i]==a[t3]*3) t3++;
		if(a[i]==a[t5]*5) t5++;
	}
	 cout<<"The 1500'th ugly number is "<<a[n]<<".\n";//cout<<"The 1500'th ugly number is <"<<a[n]<<">."<<endl;
}  

版權聲明
本文為[Five6667]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201272212546710.html

隨機推薦