# Nhắc nhở:
### Khuyến khích mọi người nên tự tìm hiểu, suy nghĩ lời giải trước khi tham khảo
### Nên đọc kỹ hướng dẫn trước khi tham khảo bài làm
___________________________________________________________________________________
### Cách 1: duyệt
Với mỗi giá trị từ $u$ đến $v$, ta sẽ đếm xem nó có bao nhiêu giá trị khác có UCLN và BCNN với nó là $u$ và $v$.
_Chúng ta có thể tối ưu bằng cách sử dụng [giải thuật Euclid](https://vi.wikipedia.org/wiki/Gi%E1%BA%A3i_thu%E1%BA%ADt_Euclid) để tăng tốc độ tìm UCLN và BCNN,
cũng như có thể chỉ duyệt các giá trị là bội của $u$._
Độ phức tạp: $O$($n^2 * \log(n)$)
### Cách 2: toán học
Chúng ta biết rằng $a * b$ = $UCLN(a,b)$ * $BCNN(a,b)$, nên thay vì duyệt từng cặp một thì
chỉ cần duyệt theo giá trị $a$ và tìm ra giá trị còn lại bằng công thức: $b$ = ($u * v$) / $a$.
(tất nhiên $a$, $b$ phải đồng thời là bội của $u$ và là ước của $u * v$).
Với mỗi cặp giá trị tìm được, ta sẽ phải kiểm tra lại để chắc chắn
$a$, $b$ có UCLN = $v$ và BCNN = $u$ (vì có trường hợp $a$ = 6, $b$ = 30, dù cùng thỏa mãn là bội của $u$ và là ước của $u * v$
nhưng không có UCLN là 3 và BCNN là 60 như test đề bài).
Nếu cặp ($a, b$) thỏa mãn cả 4 điều kiện: đều là bội của $u$, là ước của $u * v$, có UCLN là $u$ và có BCNN là $v$
thì cộng vào biến đếm.
Độ phức tạp: $O$($n * \log(n)$)
## Bài giải:
> Giải thuật: toán
> Độ phức tạp: $O$($n$ * $\log(n)$)
> Ngôn ngữ lập trình: **C++ 11**
```cpp
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int u,v,i,a,b,res=0,tich;
cin>>u>>v; tich=u*v;
for(i=u;i<=v;i+=u)
{
a=i; b=tich/i;
if (__gcd(a,b)==u&&(a*b)/__gcd(a,b)==v) res++;
}
cout<<res;
}
```
### Lưu ý: có thể có nhiều hơn một cách làm nên các bạn không nhất thiết phải làm theo lời giải
giavinh650
Created at
0 likes