資料結構
網路技術
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究C++ 中的第 N 個神奇數字
如果一個數字能被 A 或 B 整除，則稱其為神奇數字。我們要找到第 N 個神奇數字。由於答案可能非常大，因此我們將以 10^9 + 7 為模返回它。
因此，如果輸入是 N = 4，A = 4，B = 3，則輸出將為 8
為了解決此問題，我們將遵循以下步驟 −
定義一個函式 cnt()，它將取 x、A、B，
返回 (x / A) + (x / B) - (x / A 和 B 的最小公倍數)
從主方法執行以下操作 −
l := 2，r := 1^14，ret := 0
while l <= r，執行 −
mid := l + (r - l) / 2
k := cnt(mid，A，B)
如果 k < N，則 −
l := mid + 1
否則 −
ret := mid
r := mid - 1
ret := ret 模 (10^9 + 7)
返回 ret
讓我們看看以下實現以獲得更好的理解 −
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli MOD = 1e9 + 7;
class Solution {
public:
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
int lcm(int a, int b) { return (a * b) / gcd(a, b); }
lli cnt(lli x, lli A, lli B) {
return (x / A) + (x / B) - (x / lcm(A, B));
}
int nthMagicalNumber(int N, int A, int B) {
lli l = 2;
lli r = 1e14;
lli ret = 0;
while (l <= r) {
lli mid = l + (r - l) / 2;
lli k = cnt(mid, A, B);
if (k < N) {
l = mid + 1;
} else {
ret = mid;
r = mid - 1;
}
}
ret %= MOD;
return ret;
}
};
main(){
Solution ob;
cout << (ob.nthMagicalNumber(4, 4, 3));
}輸入
4, 4, 3
輸出
8
更新日期: 04-Jun-2020
187 次瀏覽
廣告