資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法學醜陋數 III C++ 程式碼
假設我們要編寫一個程式來查詢第 n 個醜陋數。醜陋數是能被 a、b 或 c 整除的正整數。所以，例如，如果 n = 3，a = 2，b = 3 和 c = 5，那麼輸出將是 4，因為醜陋數是 [2,3,4,5,6,8,9,10]，第三個是 4。
要解決這個問題，我們將按照以下步驟進行 −
建立一個名為 ok() 的方法，它將獲取 x、a、b 和 c，其作用如下 −
return (x/a) + (x/b) + (x/c) – (x/lcm(a,b)) - (x/lcm(b, c)) - (x/lcm(b,c)) - (x/lcm(a,c)) + (x/lcm(a, lcm(b,c)))
在 main 方法中，執行以下操作 −
low := 1，high := 2 * (10^9)
while low < high −
mid := low + (high - low) / 2
x := ok(mid, a, b, c)
如果 x >= n，那麼 high := mid，否則 low := mid + 1
return high
示例 (C++)
讓我們看看下面的實現，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
lli gcd(lli a, lli b){
return b == 0? a: gcd(b, a % b);
}
lli lcm(lli a, lli b){
return a * b / gcd(a, b);
}
lli ok(lli x, lli a, lli b, lli c){
return (x / a) + (x / b) + (x / c) - (x / lcm(a, b)) - (x / lcm(b, c)) - (x / lcm(a, c)) + (x / lcm(a, lcm(b, c)));
}
int nthUglyNumber(int n, int a, int b, int c) {
int low = 1;
int high = 2 * (int) 1e9;
while(low < high){
int mid = low + (high - low) / 2;
int x = ok(mid, a, b, c);
if(x>= n){
high = mid;
}
else low = mid + 1;
}
return high;
}
};
main(){
Solution ob;
cout << (ob.nthUglyNumber(3,2,3,5));
}輸入
3 2 3 5
輸出
4
更新日期：2020 年 4 月 29 日
192 次瀏覽
廣告