Solutions of GCD and LCM
Select solution language
giavinh650
Created at
5 likes
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 để 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
#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;
}