No.1164 GCD Products hard
タグ : / 解いたユーザー数 50
作問者 :
蜜蜂
/ テスター :
Mitarushi
問題文
問題文は GCD Products easy と同じですが、制約が難しくなっています。
整数 $A,B,N$ が与えられます。
$$\prod_{i_1=A}^{B}\prod_{i_2=A}^{B} \ldots \prod_{i_N=A}^{B} {\rm gcd}(i_1,i_2,\ldots,i_N)$$
を $10^9+7$ で割ったときの余りを求めてください。
ただし $\prod$ は総乗を表し、
$$\prod_{i=j}^{k}x_i = x_j \times x_{j+1} \times \cdots \times x_k$$
です。
入力
$A\ \ B\ \ N\ $
入力はすべて整数
$1 \leq A < B\leq 10^7$
$1 \leq N \leq 10^7$
出力
答えを$1$行に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 3 2
出力
6
$$
\begin{split}
\prod_{i_1=1}^{3}\prod_{i_2=1}^{3}{\rm gcd}(i_1,\ i_2) &= \left(\prod_{i_2=1}^{3}{\rm gcd}(1,\ i_2)\right) \times \left(\prod_{i_2=1}^{3}{\rm gcd}(2,\ i_2)\right) \times \left(\prod_{i_2=1}^{3}{\rm gcd}(3,\ i_2)\right) \\\\[0.5em]
&= (1\times{1}\times{1})\times(1\times{2}\times{1})\times(1\times{1}\times{3}) \\\\[0.5em]
&= 1 \times 2 \times 3 \\\\[0.5em]
&= 6
\end{split}
$$
なので、$6$ を出力します。
サンプル2
入力
11 22 11
出力
752653200
答えを $10^9+7$ で割ったときの余りを出力してください。
出典
灘校75回生中学卒業記念コンテスト: GCD Products hard
writer: Mitarushi
tester: karudano
HackerRankの規約に基づいて移植しております。一部改変したところがあります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。