Codeforces ラウンド #157 (ディビジョン 1) C. 小さなゾウと LCM (数学、DP)_PHP チュートリアル
- WBOYオリジナル
- 2016-07-13 10:14:54929ブラウズ
Codeforces Round #157 (Div. 1) C. Little Elephant と LCM （数学、dp）
C. 小さなゾウと LCM テストごとの制限時間 4秒 テストごとのメモリ制限 256メガバイト 入力 標準入力 出力 標準出力こぞうさんは、空ではない正の整数の LCM (最小公倍数) 演算が大好きです。 k 正の最小公倍数演算の結果 整数x1,?x2,?...,?xkは 各数値 xi.
で割り切れる最小の正の整数一連の整数b1,?b2,?...,?bnがあると仮定しましょう。 それらの最小公倍数を lcm(b1,?b2,?...,?bn) と表すことにします。 それらの最大値は max(b1,?b2,?...,?bn) となります。 子ゾウは、lcm(b1,?b2,?...,?bn)?=?max(b)の場合、シーケンスbが良好であるとみなします。 1、?b2、?...、?bn).
こぞうさんは、一連の整数 a1,?a2,?...,?an を持っています。 適切な整数列 b1,?b2,?...,?bn, の数を見つけるのを手伝ってください。 すべての i (1?≤?i?≤?n) にとって、次のようになります 条件が満たされます: 1?≤?bi?≤?ai。 答えはかなり大きくなる可能性があるため、1000000007 (109?+?7) で割った余りを出力します。
入力最初の行には、単一の正の整数 n (1?≤?n?≤?105) — シーケンス a 内の整数の数。 2 行目にはスペースで区切られた n が含まれます 整数 a1,?a2,?...,?an (1?≤?ai?≤?105) — シーケンスa.
出力1 行に 1 つの整数を出力します。これは、1000000007 (109?+?7) を法とする問題の答えです。
サンプルテスト入力 リーリー 出力 リーリー 入力 リーリー 出力 リーリー リーリー リーリー リーリー リーリー リーリー リーリー リーリー リーリー リーリー リーリー りー
声明：
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。