當前位置：網站首頁>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

邊欄推薦

猜你喜歡

隨機推薦