けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces Round #615 (Div. 3) F. Three Paths on a Tree

面白かった!!!
ツリーネタでまだこういうのが残ってるんだね!!!

問題へのリンク

問題概要

 N 頂点の木が与えられる。
いま、木の頂点を 3 つ選ぶ (a, b, c とする)。このとき、

  • a と b を結ぶパスに含まれている辺集合
  • b と c を結ぶパスに含まれている辺集合
  • c と a を結ぶパスに含まれている辺集合

の和集合のサイズとして考えられる最大値を求めよ。また、それを実現する具体的な 3 頂点も出力せよ。

制約

  •  3 \le N \le 2 \times 10^{5}

考えたこと

もし 3 つ選ぶのではなく 2 つだったら直径を求める問題ということになる。3 つであっても

  • 直径を求める
  • 直径から最も距離の離れた頂点を求める

とすればよいのでは...という直感がはたらく。反例はなさそうだけど一応簡単に証明してみる。

まず、ある 1 点 v が存在して、求める辺集合は

  • v-a パス
  • v-b パス
  • v-c パス

という風に分解できることに着目する。そうすると実はこの問題は


木の 1 頂点 v を決めうちしたときには、v から各点への距離のベスト 3 を a, b, c とすればよい

v を全頂点について試せばよい


ということがわかる。そう考えると全方位木 DP で解くこともできる。

ここでは直径を利用する方向へと考察を進めてみた。まず直径 p-q を 1 つとってみる。このとき、いかなる「ハブ点 v と、そこからの距離ベスト 3 の点 a, b, c」の組合せに対しても、解を悪化させることなく「直径 p-q を含む解」に変形できることがいえれば OK。以下の議論はだいぶごちゃごちゃしてしまっているけど、もう少しスマートにできるのかもしれない。

もし p-q が、v-a, v-b, v-c のいずれとも接点を持たない場合には、v からパス p-q へと向かって行ってたどり着く p-q 上の点を w とする。このとき、v-a 間と、v-b 間を削り取ってしまって、代わりに w をハブ点としてw-p 間、w-q 間、w-c 間を考えてみると、直径の定義から、元のサイズより悪化することはない。

次に、p-q が v-a, v-b, v-c のいずれかと交点をもつときを考える。p から q へと向かうときに最初に交わる点 w が v-a 上の点と仮定して一般性を失わない。このとき直径の定義から、w-q 間が w-a 間より短いことはありえないので、w-q を w-a に組み替えてしまっても良い。この時点で v-p, v-b, v-c の状態になっている。

次に q から p へと向かうときに最初に交わる点 x がどこにあるかで場合分けする

  • v-p 間の点 x で分岐するとき、v-c をなくして x-q を付け加えることで解が悪化することはない (ハブ点が v から x へと入れ替わる)

  • v-b 間の点 x で分岐するとき、x-b をなくして x-q を付け加えることで解が悪化することはない

  • v-c 間の点 x で分岐するとき、x-c をなくして x-q を付け加えることで解が悪化することはない

入り組んでしまったが、いかなる「ハブ点 v と、そこからの距離ベスト 3 の点 a, b, c」の組合せに対しても、解を悪化させることなく「直径 p-q を含む解」に変形できることがわかった。

以上をまとめると、以下のようにして解くことができる。


  • 直径を求める
  • 直径からの距離が最大の点を求める

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

using Graph = vector<vector<int>>;
int N;
Graph G;
 
struct Diameter {
    vector<int> prev;
    pair<int,int> DiameterDFS(const Graph &G, int v, int p) {
        pair<int,int> res(v, 0);
        for (int i = 0; i < (int)G[v].size(); ++i) {
            if (G[v][i] == p) continue;
            pair<int,int> tmp = DiameterDFS(G, G[v][i], v);
            tmp.second++;
            if (tmp.second > res.second) res = tmp, prev[G[v][i]] = v;
        }
        return res;
    }
 
    vector<int> solve(const vector<vector<int> > &G) {
        prev.assign((int)G.size(), -1);
        pair<int,int> leaf = DiameterDFS(G, 0, -1);
        prev.assign((int)G.size(), -1);
        pair<int,int> t = DiameterDFS(G, leaf.first, -1);
        vector<int> res;
        int cur = t.first;
        while (cur != -1) res.push_back(cur), cur = prev[cur];
        return res;
    }
};
 
vector<int> depth;
void rec(int v, int p) {
    depth[v] = depth[p] + 1;
    for (auto ch : G[v]) {
        if (ch == p) continue;
        rec(ch, v);
    }
}
 
void solve() {
    Diameter Dia;
    auto di = Dia.solve(G);

    // 直径から各頂点への距離を求める
    depth.assign(N, 0);
    for (int i = 1; i+1 < di.size(); ++i) {
        int v = di[i];
        for (auto to : G[v]) {
            if (to == di[i-1] || to == di[i+1]) continue;
            rec(to, v);
        }
    }
    int a = di[0], b = di.back(), c = -1;
    int ma = 0;
    for (int v = 0; v < N; ++v) if (chmax(ma, depth[v])) c = v;
    if (c == -1) for (int v = 0; v < N; ++v) if (v != a && v != b) c = v;
 
    printf("%d\n", ma + (int)di.size() - 1);
    printf("%d %d %d\n", a+1, b+1, c+1);
}
 
int main() {
    scanf("%d", &N);
    G.assign(N, vector<int>());
    for (int i = 0; i < N-1; ++i) {
        int u, v; scanf("%d %d", &u, &v); --u, --v;
        G[u].push_back(v); G[v].push_back(u);
    }
    solve();
}

Codeforces Round #615 (Div. 3) E. Obtain a Permutation

こういうのをちゃんと解けるようになったのは成長!

問題へのリンク

問題概要 (意訳)

以下の  M 個のクエリに答えよ。

 i 番目のクエリでは、数列  a_{1}, a_{2}, \dots, a_{N} が与えられる。この数列に以下のいずれかの操作をほどこして、 i, i+N, i+2N, \dots となるようにしたい。その最小回数を求めよ。

  •  a_{i} を任意の値に書き換える
  • 数列を circular shift する。具体的には  a_{2}, a_{3}, \dots, a_{N}, a_{1} にする。

制約

  •  1 \le M, N \le 2 \times 10^{5}
  •  1 \le N \times M \le 2 \times 10^{5}

考えたこと

 N \times M N 10^{5} 程度の大きさなので、各クエリには  O(N) O(N\log{N}) で答える必要がある。 i, i+N, i+2N, \dots b_{1}, b_{2}, \dots, b_{N} とおく。

まず言えることは、操作を行う流れとしては

  • 先に巡回操作を何回か行ってから
  • 数列の各項を書き換えていく

という風にしてよいことがわかる。そこで次のような方針が立つ。

  • 数列の巡回操作を行う回数  k を固定したときに、それによって得られる数列  a と数列  b のハミング距離を求めればよい
  • そのハミング距離 +  k の値の最小値を求めればよい

ここで逆転の発想をする。 a の各要素に対して、「巡回操作の回数が何回であれば、その値を書き換えなくて済むか」を求めていくことにする。たとえば

  • a = (3, 1, 4, 3, 5, 5)
  • b = (1, 2, 3, 4, 5, 6)

のときは、

  • a[0]: 4 回
  • a[1]: 1 回
  • a[2]: 5 回
  • a[3]: 1 回
  • a[4]: 0 回
  • a[5]: 1 回

となる。これによって、巡回操作が 0, 1, 2, 3, 4, 5 回であるようなものの登場個数がそれぞれ、1 個、3 個、0 個、0 個、1 個、1 個となっているので、総合的な操作回数は

  • 巡回操作が 0 回のとき、0 + (6 - 1) = 5 回
  • 巡回操作が 1 回のとき、1 + (6 - 3) = 4 回
  • 巡回操作が 2 回のとき、2 + (6 - 0) = 8 回
  • 巡回操作が 3 回のとき、3 + (6 - 0) = 9 回
  • 巡回操作が 4 回のとき、4 + (6 - 1) = 9 回
  • 巡回操作が 5 回のとき、5 + (6 - 1) = 10 回

ということがわかる。このうちの最小値を求めればよい。

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int calc(const vector<int> &a, map<int, int> &target) {
    int N = a.size();
    vector<int> con(N, 0);
    for (int i = 0; i < N; ++i) {
        if (target.count(a[i])) {
            int need = (N + i - target[a[i]]) % N;
            con[need]++;
        }
    }
    int res = N;
    for (int i = 0; i < N; ++i) {
        int tmp = i + (N - con[i]);
        res = min(res, tmp);
    }
    return res;
}
 
int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    vector<vector<int> > a(M, vector<int>(N));
    for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) scanf("%d", &a[j][i]);

    long long res = 0;
    for (int j = 0; j < M; ++j) {
        map<int, int> ma;
        for (int i = 0; i < N; ++i) ma[i*M + j + 1] = i;
        long long tmp = calc(a[j], ma);
        res += tmp;
    }
    printf("%lld\n", res);
}

AtCoder ABC 152 C - Low Elements (300 点)

for 文って、本当に 1 回回すだけでいろんな処理ができる!!!

問題へのリンク

問題概要

 1, 2, \dots, N の順列  p_{1}, \dots, p_{N} が与えられる。

  •  p_{i} p_{1}, \dots, p_{i} の最小値となっている

という条件を満たす  p_{i} が何個あるかを数えよ。

制約

  •  1 \le N \le 2 \times 10^{5}

考えたこと

つまり「先頭から  i 個もってきたときに、 i 番目が最小値」となっているような  i が何通りあるかを数えればよい。これは、もし  O(N^{2}) の計算量をかけてよいならば、簡単にできる。

int res = 0;
for (int i = 0; i < N; ++i) {
  int mi = N;
  for (int j = 0; j <= i; ++j) mi = min(mi, p[j]);
  if (p[i] == mi) ++res;
}
cout << res << endl;

という感じ。しかし今回はこれを  O(N) で行わなければならない。二重の for 文を使ってる余裕はないのだ。でも実は、上の実装のうち mi の計算に無駄があることがわかる。つまり、たとえば

  • i = 4 のときに、p[0], p[1], p[2], p[3] の最小値を求めているのに
  • i = 5 のときに、もう一度 p[0], p[1], p[2], p[3] も全部見た上で、さらに p[4] の値も見比べて最小値を求めている

という感じになっている。これはこんな風に高速化できる

  • i - 1 (前回) の時点での最小値を mi に対して、
  • i (今回) の時点での最小値は、新たに p[i] と見比べて mi = min(mi, p[i]) と更新してあげる

という風にすれば OK。これは実は累積和的な考え方でもある。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    int N;
    cin >> N;
    int mi = N+1, res = 0;
    for (int i = 0; i < N; ++i) {
        int p; cin >> p;
        mi = min(mi, p);
        if (mi== p) ++res;
    }
    cout << res << endl;
}

AtCoder ABC 152 D - Handstand 2 (400 点)

こういうのをスパッと解けるようになりたい

問題へのリンク

問題概要

 1 以上  N 以下の整数の組  (A, B) であって、

  •  A の最上位の値と  B の一の位の値が等しい
  •  B の最上位の値と  A の一の位の値が等しい

という条件を満たすものが何個あるかを求めよ。

制約

  •  1 \le N \le 2 \times 10^{5}

考えたこと

ペアリングの個数を数えよ、といわれたときの考察として、よくあるのが

  •  A を固定して、それに応じた  B が何個あるかを高速に数える

という方法だと思う。だが今回はこの方針で突き進もうとすると辛い気持ちになる。少し考えてみると


 A を固定したときの  B の個数は、 A の「最上位の値」と「一の位の値」のみに依存する


ということが見えてくる。 A = 12 であっても、 A = 17432 であっても、それに対応する  B の個数は等しい。よって、方針を少し変形して、以下のようにすれば OK!!!

  1. 「最上位の値  p」と「一の位の値  q」を固定したときの、それを満たす  1 以上  N 以下の整数の個数 num[  p ][  q ] を求める (この個数は  A でも  B でも等しい)

  2.  (p, q) の組としてありうる  9^{2} = 81 通りの組合せそれぞれについて、num[  p ][  q ] × num[  p ][  q ] の値を合算する

num[  p ][  q ] は、単純に  1 から  N までの値それぞれについて、「最上位の値」と「一の位の値」を求めてあげて、それに応じた num の値をインクリメントすれば OK。計算量は  O(N)

#include <iostream>
#include <vector>
#include <string>
using namespace std;
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

int main() {
    int N;
    cin >> N;
    long long res = 0;
    vector<vector<long long>> num(10, vector<long long>(10, 0));
    for (int n = 1; n <= N; ++n) {
        vector<int> d;
        int nn = n;
        while (nn) {
            d.push_back(nn % 10);
            nn /= 10;
        }
        int a = d[0];
        int b = d.back();
        if (!a || !b) continue;
        ++num[a][b];
    }
    for (int a = 1; a < 10; ++a) {
        for (int b = 1; b < 10; ++b) {
            res += num[a][b] * num[b][a];
        }
    }
    cout << res << endl;
}

AtCoder ABC 152 E - Flatten (500 点)

「〜の最小値を求めてください」「ただし 1000000007 で割ったあまりで」
...この設定の歪さを見ると、不思議な気持ちになる

問題へのリンク

問題概要

 N 個の正の整数  A_{1}, A_{2}, \dots, A_{N} が与えられる。以下の条件を満たす正の整数列  B_{1}, B_{2}, \dots, B_{N} をすべて考えたときの、 B_{1} + B_{2} + \dots + B_{N} の最小値を求めよ (1000000007 で割ったあまりで)

  •  A_{1} \times B_{1} = A_{2} \times B_{2} = \dots = A_{N} \times B_{N} が成立

制約

  •  1 \le N \le 10^{4}
  •  1 \le A_{i} \le 10^{6}

考えたこと

1000000007 で割ったあまりを求めよ、というのは通常は「数え上げ問題」で問われる。「最小値を求めよ」という問題でそれが要求されるのは珍しい。

というのも、たとえば 6 と 1000000008 が答えの候補として絞れたとして、実際の答えは 6 であるば、mod をとってしまうとそれぞれ 6 と 1 になってしまって大小関係がよくわからなくなってしまう。

なので、「最小値を求めよ」という問題で 1000000007 で割ったあまりを要求されたら、かなりの確率で「答えを導くなんらかの計算式が導出できそう」という予感がする。その式が導けたならば、いつも通り、途中過程を 1000000007 で割りながら計算していけばよい。

さて、少し考えると、

  • 等しい数を  L = A_{1} \times B_{1} = A_{2} \times B_{2} = \dots = A_{N} \times B_{N} とおいてみる
  • このとき、 L A_{1}, A_{2}, \dots, A_{N} を割り切る、つまり  L A_{1}, A_{2}, \dots, A_{N} の公倍数である
  •  L は小さければ小さいほどよいので、 A_{1}, A_{2}, \dots, A_{N}最小公倍数とすればよい

ということがわかる。以上から、問題は以下のことに帰着された。


  •  A_{1}, A_{2}, \dots, A_{N} の最小公倍数を求めて  L として

  •  \frac{L}{B_{1}} + \frac{L}{B_{2}} + \dots + \frac{L}{B_{N}} が答え


しかし  L は 104 個もの値の最小公倍数ということで、ものすごく大きな整数になりうる。具体的には、仮に  A がすべて互いに素であるとすると、 6 \times 10^{4} 桁くらいになりうるわけだ ( A_{i} \le 10^{6} なので)。こんな  L を真っ向から扱うのは大変だ。

1. L を 1000000007 で割ったあまりを求める

まず大前提として、 \frac{L}{B_{1}} + \frac{L}{B_{2}} + \dots + \frac{L}{B_{N}} を計算したいと思ったとき、 L を 1000000007 で割ったあまりとしてしまうと、 B_{1} とかで割れなくなってしまうのでは...という不安を抱いた方は多いかもしれない。

しかし!!!その心配はない!!!!!mod. 1000000007 の世界で  L ÷ B_{i} を計算すればよいのだ!!!その考え方はここにも書いた

qiita.com

さて、3 つ以上の整数の最小公倍数の求め方を考えよう。たとえば

  •  120 = 2^{3} \times 3^{1} \times 5^{1}
  •  63 = 3^{2} \times 7^{1}
  •  250 = 2^{1} \times 5^{3}

の最小公倍数は、それぞれ素因数分解したときの各素数の「指数」の最大をとっていくことで求められ、

  •  L = 2^{3} \times 3^{2} \times 5^{3} \times 7^{1} = 63000

となる。まとめると


  •  A_{1}, A_{2}, \dots, A_{N}素因数分解をする
  • 各素因数ごとに指数の最大値を拾って掛け算していくことで、最小公倍数  L を求める (この過程で 1000000007 で割っていってよい)
  • mod. 1000000007 で  \frac{L}{B_{1}} + \frac{L}{B_{2}} + \dots + \frac{L}{B_{N}} を計算する

という風にして AC することができる。計算量は、 A_{i} の最大値を  M として  O(N\sqrt{M})

#include <iostream>
#include <vector>
#include <string>
using namespace std;
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

// modint: mod 計算を int を扱うように扱える構造体
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};
using mint = Fp<1000000007>;

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

int main() {
    int N; cin >> N;
    vector<long long> A(N);
    vector<long long> num(1100000, 0);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        auto pf = prime_factorize(A[i]);
        for (auto p : pf) num[p.first] = max(num[p.first], p.second);
    }

    mint LCM = 1;
    for (int v = 2; v < 1100000; ++v) {
        LCM *= modpow(mint(v), num[v]);
    }

    mint res = 0;
    for (auto a : A) {
        res += LCM / a;
    }
    cout << res << endl;
}

2. 素因数分解を高速化する

今回は  A_{1}, A_{2}, \dots, A_{N} を愚直に素因数分解したが、ここを高速化することを考える。実は  M = 10^{6} くらいとして、  1, 2, 3, \dots, M をまとめて高速に素因数分解してしまう方法がある。大昔、osa_k 法とかよばれていた方法だ。エラトスネテスの篩が有効活用できる。

エラトステネスの篩は、 M 以下の素数を列挙する方法であるが、ついでに以下の配列を作成することができる:

  • min_factor[ n ] := n を割り切る最小の素数

ここまでの前処理を  O(N \log\log{N}) でできる。この前処理を行っておくと、 M 以下の整数  n素因数分解を、以下のように  O(\log{n}) でできる。

  • 「n を p = min_factor[ n ] で割れるだけ割る」というのを n = 1 となるまで繰り返す

たとえば n = 120 だったら、

  • min_factor[120] = 2 なので、2 で割れるだけ割ると 15 になる
  • min_factor[15] = 3 なので、3 で割れるだけ割ると 5 になる
  • min_factor[5] = 5 なので、5 で割れるだけ割ると 1 になる

という感じ。計算量は  O(M\log\log{M} + N \log{M})。なお、editorial には  O(M + N\log{M}) と書いてあるけど、これは、エラトステネスの篩の処理を線形時間で実行するマニアックなアルゴリズムを使った場合の話と思われる。

#include <iostream>
#include <vector>
using namespace std;


// modint: mod 計算を int を扱うように扱える構造体
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};
using mint = Fp<1000000007>;
 

// エラトスネテスの篩
struct Eratos {
    vector<int> primes;
    vector<bool> isprime;
    vector<int> min_factor;

    Eratos(int MAX) : primes(),
                      isprime(MAX+1, true),
                      min_factor(MAX+1, -1) {
        isprime[0] = isprime[1] = false;
        min_factor[0] = 0, min_factor[1] = 1;
        for (int i = 2; i <= MAX; ++i) {
            if (!isprime[i]) continue;
            primes.push_back(i);
            min_factor[i] = i;
            for (int j = i*2; j <= MAX; j += i) {
                isprime[j] = false;
                if (min_factor[j] == -1) min_factor[j] = i;
            }
        }
    }

    // prime factorization
    vector<pair<int,int>> prime_factorize(int n) {
        vector<pair<int,int> > res;
        while (n != 1) {
            int prime = min_factor[n];
            int exp = 0;
            while (min_factor[n] == prime) {
                ++exp;
                n /= prime;
            }
            res.push_back(make_pair(prime, exp));
        }
        return res;
    }
};


int main() {
    int N; cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    Eratos er(1100000);    
    vector<int> num(1100000, 0);
    for (int i = 0; i < N; ++i) {
        auto pf = er.prime_factorize(A[i]);
        for (auto p : pf) num[p.first] = max(num[p.first], p.second);
    }
 
    mint LCM = 1;
    for (int v = 2; v < 1100000; ++v) {
        LCM *= modpow(mint(v), num[v]);
    }
 
    mint res = 0;
    for (auto a : A) {
        res += LCM / a;
    }
    cout << res << endl;
}