Số thứ n
Xem PDF
Điểm:
400 (p)
Thời gian:
1.0s
Bộ nhớ:
1023M
Input:
bàn phím
Output:
màn hình
Bạn được cho 2 số nguyên dương \(a\) và \(b\).
Viết chương trình tìm số thứ \(n\) chia hết cho \(a\) hoặc \(b\).
Input
- Dòng đâu tiên chứa số nguyên dương \(T\) \((T \leq 10^5)\) - là số câu hỏi.
- \(T\) dòng, mỗi dòng chứa 3 số nguyên dương \(a, b, n\) \((a,b \leq 10^4, N \leq 10^9)\).
Output
- Gồm \(T\) dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.
Example
Test 1
Input
1
2 3 10Output
15Note
Giải thích Những số chia hết cho \(2\) hoặc cho \(3\) là \(2, 3, 4, 6, 8, 9, 10, 12, 14, 15, ....\)
Bình luận
include <bits/stdc++.h>
using namespace std;
long long g(long long n,long long a,long long b) {
return n/b+n/a-n/(a*b/__gcd(a,b));
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
long long t;
cin>>t;
for (int i=1; i<=t; i++) {
int a,b,n;
cin>>a>>b>>n;
long long L =1;
long long R=1e18;
while (1) {
if (L==R) break;
if (L==R-1) {
if (g(L,a,b)<n) L=R; break; } long long m=(L+R)/2; if (g(m,a,b)>=n) R=m;
else L=m;
}
cout<<L<<'\n';
}
return 0;
} than khảo code của mình đi uy tín lắm
4 bình luận nữa