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

题目

对于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;
	}
}