Bedao Mini Contest 25 - Ước chia hết
Xem dạng PDF
Gửi bài giải
Điểm:
0,01 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho bốn số nguyên dương ~N~, ~A~, ~B~, ~C~. Đếm số lượng ước nguyên dương của ~N~ chia hết ít nhất hai trong ba số ~A~, ~B~, ~C~.
Input
Gồm ~4~ số nguyên dương ~N~, ~A~, ~B~, ~C~ ~(A, B, C, N \leq 10^{18})~.
Output
Ghi ra kết quả tìm được.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~20\%~ | ~N \leq 10^6~ |
| 2 | ~40\%~ | ~N \leq 10^{12}~ |
| 3 | ~40\%~ | ~10^6 \leq A, B, C~ |
Sample Input 1
100 2 3 5
Sample Output 1
4
Sample Input 2
20 1 2 5
Sample Output 2
5
Notes
Ở ví dụ 1, ta sẽ có những số thoả mãn là ~10, 20, 50, 100~.
Ở ví dụ 2, ta sẽ có những số thoả mãn là ~2, 4, 5, 10, 20~.
Bình luận
You are my sensei :D
iu mỗi Yu thôi
CODE an duoc toi sub2 :((, sub3 chiu
include <bits/stdc++.h>
using namespace std; long long du(long long n,long long a,long long b,long long c){ long long cnt=0; for (long long i=1;i*i<=n;i++){ if (n%i==0){ if (i%a==0 && i%b==0 || i%a==0 && i%c==0 || i%b==0 && i%c==0) cnt++; if ((i!=n/i) && ((n/i)%a==0 && (n/i)%b==0 || (n/i)%a==0 && (n/i)%c==0 || (n/i)%b==0 && (n/i)%c==0)) cnt++;
} } return cnt; } int main(){ iosbase::syncwith_stdio(0); cin.tie(0); cout.tie(0); long long n,a,b,c; cin>>n>>a>>b>>c; cout<<du(n,a,b,c); }
Gợi ý: 1)bruteforce hơn 1e9 thường tle 2)do ước thỏa mãn 2 trong 3 biến nên bạn tìm cách để check ước dựa vào 2 trong 3 biến đó 3)N,A,B,C cấu tạo từ cái gì?
hgjghj
bài này làm sao để ko tle vậy