No.1164 GCD Products hard

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.1164 GCD Products hard

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 51
作問者 :

蜜蜂 / テスター :

Mitarushi

6 ProblemId : 4962 / 自分の提出

問題文最終更新日: 2020-08-13 23:04:23

問題文

問題文は GCD Products easy と同じですが、制約が難しくなっています。
整数 $A, B, N$ が与えられます。
$\prod_{i_{1} = A}^{B} \prod_{i_{2} = A}^{B} \dots \prod_{i_{N} = A}^{B} g c d (i_{1}, i_{2}, \dots, i_{N})$
を $10^{9} + 7$ で割ったときの余りを求めてください。
ただし $\prod$ は総乗を表し、
$\prod_{i = j}^{k} x_{i} = x_{j} \times x_{j + 1} \times \dots \times x_{k}$
です。

入力

 $A B N$

入力はすべて整数
$1 \leq A < B \leq 10^{7}$
$1 \leq N \leq 10^{7}$

出力

答えを $1$ 行に出力してください。
最後に改行してください。

サンプル

サンプル1

入力

1 3 2

出力

$\begin{aligned} \prod_{i_{1} = 1}^{3} \prod_{i_{2} = 1}^{3} g c d (i_{1}, i_{2}) & = (\prod_{i_{2} = 1}^{3} g c d (1, i_{2})) \times (\prod_{i_{2} = 1}^{3} g c d (2, i_{2})) \times (\prod_{i_{2} = 1}^{3} g c d (3, i_{2})) \\ = (1 \times 1 \times 1) \times (1 \times 2 \times 1) \times (1 \times 1 \times 3) \\ = 1 \times 2 \times 3 \\ = 6 \end{aligned}$
なので、 $6$ を出力します。

サンプル2

入力

11 22 11

出力

752653200

答えを $10^{9} + 7$ で割ったときの余りを出力してください。

出典

灘校75回生中学卒業記念コンテスト: GCD Products hard
writer: Mitarushi
tester: karudano
HackerRankの規約に基づいて移植しております。一部改変したところがあります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。

yukicoder

No.1164 GCD Products hard

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

出典