CodeForces Round 705-D GCD of an Array 数论 乱搞 or 线段树 + 质因子分解科技
题意
给定数组(a)，(q)个询问，每次询问对(pos)乘上(x)，询问全局(gcd)
[1 leq n ,q leq 2e5\
1 leq a_i leq 2e5\
1 leq x leq 2e5
]
分析
乱搞
此题有以下事实:
1.全局GCD不会变小
2.全局GCD会改变当且仅当 某个公共质因子的最小次数发生了改变
3.基于1，只需要关注乘上一个数，这个数的质因子的变化
因此，事实上我们只需要维护所有值域内的质因子的指数，我们知道这个指数不会非常大。
因此不妨用(STL::map)维护第(i)个数的质因子(d)的出现次数。
用(STL::multiset)维护每个位置质因子(d)的指数，如果为(0)，不加入就好了
统计答案时，只需要判断(x)的质因子(p)，是否在所有数中出现((set.size() = n))，且它的最小值是否改变，假设改变了(del)，它对答案的贡献就是(p^{del})
时间复杂度(O(nlog^2n))
代码
const ll MOD = 1e9 + 7;
const int maxn = 2e5 + 5;
ll ksm(ll a,ll b,ll m){
ll ans = 1;
ll base = a;
while(b){
if(b & 1) {
ans *= base;
ans %= MOD;
}
base *= base;
base %= MOD;
b >>= 1;
}
return ans;
}
int nxt[maxn];
multiset<int> cnt[maxn];
map<int,int> mp[maxn];
ll ans;
int n;
void init(){
for(int i = 2;i < maxn;i++)
if(!nxt[i]) {
nxt[i] = i;
if(i > 10000) continue;
for(int j = i * i;j < maxn;j += i){
if(!nxt[j]) nxt[j] = i;
}
}
}
void add(int i,int x){
while(x != 1) {
int d = nxt[x];
int cur = 0;
while(nxt[x] == d) cur++,x /= nxt[x];
int last = mp[i][d];
mp[i][d] += cur;
int l = 0;
if(cnt[d].size() == n)
l = *cnt[d].begin();
if(last)
cnt[d].erase(cnt[d].find(last));
cnt[d].insert(cur + last);
if(cnt[d].size() == n) {
int pow = max(0,*cnt[d].begin() - l);
ans *= ksm(d,pow,MOD);
ans %= MOD;
}
}
}
int main(){
init();
n = rd();
int q = rd();
ans = 1;
for(int i = 1;i <= n;i++){
int x = rd();
add(i,x);
}
while(q--){
int x = rd();
ll y = rd();
add(x,y);
cout << ans << '
';
}
}
线段树
感觉线段树反而是比较直觉的做法？？
但是此题好像不太好维护
我们对每个节点维护区间GCD，这段范围内的多余的质因子个数。
维护答案时，只需要对(x)质因子分解，考虑每个质因子和当前节点多余的质因子取(min)，就得到了对答案的贡献。
update自底向上更新的时候只需要用上一次对答案的贡献更新即可，其他是不可能对GCD产生影响的。
感觉这种维护方法比较特殊，记录一下。
注意质因子分解的时候如果用朴素的试除法会(T),可以用一种(logn)的做法。
复杂度大约(O(nlog^3n))
#include<bits/stdc++.h>
#define eps 1e-4
#define equals(a,b) (fabs(a - b) < eps)
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
typedef long long ll;
ll rd(){
ll x = 0;
int f =1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
const ll MOD = 1e9 + 7;
ll ksm(ll a,ll b,ll m){
ll ans = 1;
ll base = a;
while(b){
if(b & 1) {
ans *= base;
ans %= MOD;
}
base *= base;
base %= MOD;
b >>= 1;
}
return ans;
}
const int maxn = 2e5 + 5;
ll spf[maxn];
void sieve() {
spf[1] = 1ll;
for (ll i=2ll; i< maxn; i++) spf[i] = i;
for (ll i=4ll; i< maxn; i+=2ll) spf[i] = 2ll;
for (ll i=3ll; i * i < maxn; i++) {
if (spf[i] == i) {
for (ll j = i * i; j< maxn; j += i)
if (spf[j]==j)
spf[j] = i;
}
}
}
void getfac(vector<pii>& v,ll x){
while(x > 1) {
int cnt = 0;
int s = spf[x];
while(spf[x] == s) {
cnt++;
x /= s;
}
v.push_back(make_pair(s,cnt));
}
}
ll gcd(ll a,ll b){
return b == 0 ? a : gcd(b,a % b);
}
struct SegmentTree{
struct Node{
ll g;
map<ll,int> mp;
};
vector<Node> node;
SegmentTree(int n):node((n + 1) << 2) {};
ll addr(int i,ll x){
vector<pii> v;
ll tmp = 1;
getfac(v,x);
for(auto it:v){
int pre = node[i].mp[it.fi];
if(pre < 0) {
tmp *= ksm(it.fi,min(abs(pre),abs(it.se)),MOD);
tmp %= MOD;
}
node[i].mp[it.fi] = pre + it.se;
}
node[i].g *= tmp;
node[i].g %= MOD;
return tmp;
}
void build(int i,int l,int r){
if(l == r) {
node[i].g = rd();
return;
}
int mid = l + r >> 1;
build(i << 1,l,mid);
build(i << 1|1,mid + 1,r);
node[i].g = gcd(node[i << 1].g,node[i << 1|1].g);
addl(i,node[i << 1].g / node[i].g);
addr(i,node[i << 1|1].g / node[i].g);
}
ll update(int i,int l,int r,int pos,ll x){
if(l == r) {
node[i].g = (node[i].g * x) % MOD;
return x;
}
int mid = l + r >> 1;
if(pos <= mid) {
ll v = update(i << 1,l,mid,pos,x);
return addl(i,v);
}
else {
ll v = update(i << 1|1,mid + 1,r,pos,x);
return addr(i,v);
}
}
};
int main(){
sieve();
int n = rd();
int q = rd();
SegmentTree seg(n);
seg.build(1,1,n);
while(q--){
int pos = rd();
int x = rd();
seg.update(1,1,n,pos,x);
cout << seg.node[1].g << '
';
}
}