2021-2022-2 ACM集训队每周程序设计竞赛（12） - 问题 E: 有一点大的最小公倍数 - 题解

给你 n n n 个正整数 S S S，需要你求出这 n n n 个数的最小公倍数 r e s res res，然后再求 ∑ i = 1 n r e s S [ i ] % ( 1 0 9 + 7 ) sumlimits_{i=1}^{n}{frac{res}{S[i]}}%(10^{9}+7) i=1∑n​S[i]res​%(109+7) 的值即可。

整体题意还是比较清楚的，只需要求出 n n n 个数的最小公倍数，然后运用一些逆元的思想即可。

涉及到模数的运算，就肯定不能直接上 g c d gcd gcd 了，需要将这 n n n 个数都分解质因数，然后再遍历所有出现过的质数的最多次数，将其相乘，就求出了 n n n 个数的最小公倍数。
然后剩下的步骤就好说多了。

时间复杂度： O （ n ∗ log ⁡ n ） O（n*log{n}） O（n∗logn）

#include 
using namespace std;
const int mod = 1e9 + 7;
int n;
int s[10010];
int d[1000010];

int qpow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1)
			res = (long long)res * a % mod;
		a = (long long)a * a % mod;
		b >>= 1;
	}
	return res;
}

int main() {

	cin >> n;

	for (int j = 1, x; j <= n; j++) {
		scanf("%d", &s[j]);
		x = s[j];

		for (int i = 2; i <= x / i; i++)
			if (x % i == 0) {
				int cnt = 0;

				while (x % i == 0) {
					x /= i;
					cnt++;
				}
				d[i] = max(d[i], cnt);
			}
		if (x > 1)
			d[x] = max(d[x], 1);
	}

	int res = 1;
	for (int i = 2; i <= 1000000; i++)
		if (d[i])
			res = (long long)res * qpow(i, d[i]) % mod;

	int ans = 0;
	for (int i = 1; i <= n; i++)
		ans = (ans + (long long)res * qpow(s[i], mod - 2) % mod) % mod;
	cout << ans;

	return 0;
}