Hướng dẫn giải của Bội chung của dãy
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Ý tưởng
Xét nhân tử nguyên tố ~p~, thì số mũ của ~p~ trong Bội chung của dãy sẽ là số mũ lớn nhất của p khi phân tích các ~a_i~ thành thừa số nguyên tố.
Vậy với mỗi lần nhân ~x~ vào vị trí ~a_i~, ta cần kiểm tra các nhân tử ~p~ của ~x~, khi nhân ~x~ vào ~a_i~ có khiến số mũ lớn nhất đó thay đổi không, nếu có ta sẽ nhân Bội chung lên một lượng tương ứng Số nhân tử khi phân tích một số x thành thừa số nguyên tố sẽ không vượt quá ~log(x)~
Độ phức tạp : ~O(AloglogA + (n+q)logA)~ với ~A~ là giá trị tối đa của ~a_i, x~
Lời giải tham khảo
Tác giả:
/*
www.youtube.com/YugiHackerChannel
oj.vnoi.info/user/YugiHackerKhongCopCode
*/
#include<bits/stdc++.h>
#define el cout<<"\n"
#define f0(i,n) for(int i=0;i<n;++i)
#define f1(i,n) for(int i=1;i<=n;++i)
#define maxn 100005
#define MOD 1000000007
using namespace std;
int n, q, a[maxn], d[maxn], ma[maxn];
map <int, int> cnt[maxn];
long long ans = 1;
main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
for (int i=2; i*i<maxn; ++i)
for (int j=i*i; j<maxn; j+=i) if (d[j] == 0) d[j] = i;
for (int i=2; i<maxn; ++i) if (d[i] == 0) d[i] = i;
cin >> n >> q;
f1 (i, n)
{
cin >> a[i];
while (a[i] > 1)
{
int k = d[a[i]];
int cur = 0;
while (a[i] % k == 0) cur++, a[i]/=k;
cnt[i][k] += cur;
if (cnt[i][k] > ma[k])
{
f1 (_, cnt[i][k]-ma[k]) (ans *= k) %= MOD;
ma[k] = max(ma[k], cur);
}
}
}
while (q--)
{
int i, val; cin >> i >> val;
while (val > 1)
{
int k = d[val];
int cur = 0;
while (val % k == 0) cur++, val /= k;
cnt[i][k] += cur;
if (cnt[i][k] > ma[k])
{
f1 (_, cnt[i][k]-ma[k]) (ans *= k) %= MOD;
ma[k] = max(ma[k], cnt[i][k]);
}
}
cout << ans; el;
}
}
Bình luận