สมมุติว่าเราต้องเขียนโปรแกรมหาเลขน่าเกลียดตัวที่ 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 ซึ่งจะทำหน้าที่ดังต่อไปนี้ -
-
ผลตอบแทน (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)))
-
จากวิธีหลัก ให้ทำดังนี้ -
-
ต่ำ :=1, สูง :=2 * (10^9)
-
ในขณะที่ต่ำ <สูง −
-
กลาง :=ต่ำ + (สูง - ต่ำ) / 2
-
x :=ตกลง(กลาง, ก, ข, ค)
-
ถ้า x>=n แสดงว่าสูง :=กลาง มิฉะนั้น ต่ำ :=กลาง + 1
-
-
ผลตอบแทนสูง
ตัวอย่าง (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
