Solutions of Largest common divisor
Select solution language
giavinh650
Created at
17 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
Hướng dẫn này sẽ chỉ tập trung vào 1 cách làm duy nhất, nên nếu các bạn có cách làm khác thì cũng không sao!
Bước 1: Cải tiến sàng nguyên tố thành sàng ước nguyên tố
Tương tự như cách chúng ta làm với sàng nguyên tố, nhưng thay vì đánh dấu các giá trị là hợp số, ta sẽ đánh dấu nó bằng ước nguyên tố của nó.
void sieve(int n)
{
int i,j;
for(i=2;i<=n;i++)
{
if (f[i]==0)
{
for(j=i;j<=n;j+=i) f[j]=i;
}
}
}Độ phức tạp: $O$($n * \log(n)$)
Bước 2: Phân tích thừa số nguyên tố với sàng ước nguyên tố
Sau khi chúng ta tạo ra sàng ước nguyên tố, ta có thể nhanh chóng phân tích thừa số nguyên tố các giá trị $A_i$ với tốc độ $O$($\log(n)$) (nhanh hơn so với việc chỉ phân tích thừa số nguyên tố bình thường, có tốc độ là $O$($\sqrt{n}$) )
while (a[i]>1)
{
mp[f[a[i]]]++; a[i]/=f[a[i]];
// mp[] là mảng đếm số mũ của các cơ số (tức ước nguyên tố) của các phần tử
// sau mỗi lần thêm, ta sẽ chia giá trị cho chính ước nguyên tố của nó và lặp lại
// chỉ kết thúc vòng lặp khi toàn bộ các ước nguyên tố đã được lấy
}Độ phức tạp: $O$($n * \log(n)$)
Bước 3: Lưu số mũ lớn nhất của các thừa số nguyên tố sau mỗi lần phân tích
Bước này sẽ giúp chúng ta lấy được các giá trị cần thiết sau khi phân tích thừa số nguyên tố của các giá trị $A_i$, và sẽ dùng để tính BCNN của toàn bộ dãy số.
for(it=mp.begin();it!=mp.end();it++)
{
if ((*it).second>f1[(*it).first]) f1[(*it).first]=(*it).second;
//nếu số mũ của cơ số đang xét lớn hơn số mũ lớn nhất của cùng cơ số trước
//thì ta sẽ cập nhật max vào 1 mảng lưu số mũ của các cơ số
//trong trường hợp này thì f1[] là mảng lưu số mũ của các cơ số
}Độ phức tạp: $O$($n * \log(n)$)
Chúng ta có công thức tính BCNN là $(p_1 + 1) * (p_2 + 1) * … * (p_n + 1)$, với $p_1, p_2, …, p_n$ là số mũ của các ước nguyên tố riêng biệt. Và với các bước trên, chúng ta đã có được các giá trị $p_1, p_2, …, p_n$ rồi, nên giờ chỉ việc tính là xong.
Bước 4: Tính kết quả
Ta có công thức: $(a * b)$ mod $c$ = (($a$ mod $c$) * ($b$ mod $c$)) mod $c$ (với mod là phép chia lấy dư).
Do đó, với mỗi lần duyệt ta có thể liên tục mod để tránh việc tích bị tràn (vượt quá giới hạn của ngôn ngữ lập trình).
Tuy nhiên, số lượng số mũ có thể lớn (~ $10^7$) nên chúng ta có thể áp dụng lũy thừa nhị phân để tăng tốc độ tính toán:
int powmod(int a, int n, int mod)
{
int res=1;
while (n)
{
if (n%2) res=(res*a)%mod;
a=(a*a)%mod;
n/=2;
}
return res;
}Độ phức tạp $O$($\log(n)$) cho mỗi lần tính
Bài giải:
> Giải thuật: sàng ước nguyên tố + phân tích thừa số nguyên tố + lũy thừa nhị phâ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;
const int mod=1000000007,N=1e5+10; int a[N],f[N]={},f1[N]={};
map<int,int> mp; map<int,int>::iterator it;
void sieve(int n)
{
int i,j;
for(i=2;i<=n;i++)
{
if (f[i]==0)
{
for(j=i;j<=n;j+=i) f[j]=i;
}
}
}
int powmod(int a, int n, int mod)
{
int res=1;
while (n)
{
if (n%2) res=(res*a)%mod;
a=(a*a)%mod;
n/=2;
}
return res;
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n,i,res=1,x,j;
sieve(N);
cin>>n;
for(i=1;i<=n;i++)
{
mp.clear();
cin>>a[i];
while (a[i]>1)
{
mp[f[a[i]]]++; a[i]/=f[a[i]];
}
for(it=mp.begin();it!=mp.end();it++)
{
if ((*it).second>f1[(*it).first]) f1[(*it).first]=(*it).second;
}
}
for(i=1;i<=N-10;i++) res=(res*powmod(i,f1[i],mod))%mod;
cout<<res;
}