算法
(枚举约数) $O(1e6 + n\log 1e6)$
令 $X = A_iB_i$
注意到,$\sum B_i$ 最小 $\Leftrightarrow$ $X$ 最小,而 $X$ 又是 $(A_1, A_2, \cdots, A_n)$ 的公倍数,所以只要让 $X$ 为 $(A_1, A_2, \cdots, A_n)$ 的最小公倍数即可,于是 $B_i = \frac{X}{A_i}$。然而 $X$ 可能很大,我们并不能直接计算。然后我们想到 算术基本定理
刚好可以解决这个问题, 于是对每个数进行素因子分解, 然后对于其中的每个素因子取幂指数最大的那个即可。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define fi first
#define se second
using std::cin;
using std::cout;
using std::max;
using std::map;
using std::vector;
using ll = long long;
using P = std::pair<int, int>;
const int N = 1000005;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod){}
mint operator-() const { return mint(-x);}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
mint res(*this);
return res+=a;
}
mint operator-(const mint a) const {
mint res(*this);
return res-=a;
}
mint operator*(const mint a) const {
mint res(*this);
return res*=a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return (*this) *= a.inv();
}
mint operator/(const mint a) const {
mint res(*this);
return res/=a;
}
};
struct Sieve {
int n;
vector<int> f, primes;
Sieve(int n = 1): n(n), f(n + 1) {
f[0] = f[1] = -1;
for (ll i = 2; i <= n; ++i) {
if (f[i]) continue;
primes.push_back(i);
f[i] = i;
for (ll j = i * i; j <= n; j += i) {
if (!f[j]) f[j] = i;
}
}
}
bool isPrime(int x) { return f[x] == x; }
vector<int> factorList(int x) {
vector<int> res;
while (x != 1) {
res.push_back(f[x]);
x /= f[x];
}
return res;
}
vector<P> factor(int x) {
vector<int> fl = factorList(x);
if (fl.size() == 0) return {};
vector<P> res(1, P(fl[0], 0));
for (int p : fl) {
if (res.back().fi == p) {
res.back().se++;
}
else {
res.emplace_back(p, 1);
}
}
return res;
}
};
int main() {
Sieve sieve(1e6);
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
map<int, int> mp;
rep(i, n) {
auto f = sieve.factor(a[i]);
for (auto p : f) {
mp[p.fi] = max(mp[p.fi], p.se);
}
}
mint lcm = 1;
for (auto p : mp) {
rep(i, p.se) {
lcm *= p.fi;
}
}
mint ans;
rep(i, n) {
mint b = lcm / a[i];
ans += b;
}
cout << ans.x << '\n';
return 0;
}