D. GCD of an Array（数论、multiset）

痛定思痛。 2021-07-16 15:56 337阅读 0赞

[题目][Link 1]

对于n个元素的gcd，将每个元素质因数分解，对于一个质数如果每个元素都有其作为因数，那么这个质数p对答案的贡献为p^(所有元素分成质因数相乘中p的最小次方）  
a1=p1^b1 …\* pi^c1\* … pm^d1  
a2=p1^b2 … \* pi^c2 \*… pm^d2  
…  
an=pn ^ bn…\*pi ^ cn … pm^dn

如质数pi，其对答案贡献为 pi^(min(c1,c2,c3…,cn))，将质因数的贡献相乘即为最终答案。

如果某个质因数不是n个元素都有，那么其没有产生贡献。所以我们需要做的就是将每个元素或相乘数质因数分解，并且还要记录第i个元素各种质因数的次方数，和每个值质因数在n个元素中出现次数，如果在n个元素中出现还要快速求出其在n个元素中的最小次数，并进行增删改。

用map可以用来纪录各个元素的质因数的次方数，multiset可以快速求出n个元素中某质因数的最小值、记录出现次数，如果要改变mutiset某个元素erase掉原值，再insert进新值也和改变值的功能相同。我个人会把multiset当作一个优先队列使用，且还支持查和改。

Code:

#include<iostream>
    #include<map>
    #include<cmath>
    #include<set>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    const int Mod = 1e9 + 7;
    map<int, int> ma[Max];
    multiset<int> se[Max];
    ll d = 1, n;
    
    ll qpow(ll a, ll b) { 
    	ll ans = 1, base = a;
    	while (b) { 
    		if (b & 1) ans = ans * base % Mod;
    		base = base * base % Mod;
    		b >>= 1;
    	}
    	return ans;
    }
    
    ll inv(int n){ return qpow(n, Mod - 2);}
    
    void add(int k, int i, int num)
    { 
    	if (se[i].size() == n)
    	{ 
    		d = d * inv(qpow(i, *se[i].begin())) % Mod;
    		se[i].erase(se[i].find(ma[k][i]));
    		se[i].insert(num + ma[k][i]);
    		d = d * qpow(i, *se[i].begin()) % Mod;
    	}
    	else
    	{ 
    		if (se[i].find(ma[k][i]) != se[i].end())se[i].erase(se[i].find(ma[k][i]));
    		se[i].insert(num + ma[k][i]);
    		if (se[i].size() == n)d = d * qpow(i, *se[i].begin()) % Mod;
    	}
    	ma[k][i] += num;
    }
    
    void divid(int k,int mul)
    { 
    	for (int i = 2;i * i <= mul;i++)
    	{ 
    		int num = 0;
    		if (mul % i == 0)
    		{ 
    			while (mul % i == 0)
    			{ 
    				num++;
    				mul /= i;
    			}
    			add(k, i, num);
    		}
    	}
    	if (mul != 1)add(k, mul, 1);
    }
    
    int main()
    { 
    	int q;cin >> n >> q;
    	for (int i = 1;i <= n;i++)
    	{ 
    		int a;cin >> a;divid(i, a);
    	}
    	for (int i = 1;i <= q;i++)
    	{ 
    		int a,b;cin >> a>>b;divid(a, b);
    		cout << d << endl;
    	}
    }

[Link 1]: https://codeforc.es/problemset/problem/1493/D