問題一覧 >
通常問題
No.2181 LRM Question 2
問題文最終更新日: 2024-11-28 20:40:38
問題文
正整数 L,R,M が与えられます。次の値を M で割った余りを求めてください。
n=L∑R((i=1∏ni21)i=1∑n−1(j=1∏i(n−j+1)2j=i+1∏nj2))
なお、本問の制約下において、上式の値は必ず非負整数となることが保証されます。
∑,∏ の定義(クリックで展開)
長さ n の数列 a=(a1,a2,…,an)
に対して、i=l∑rai 及び i=l∏rai
は次のように定義されます。
i=l∑rai=al+al+1+⋯+ar
i=l∏rai=al×al+1×⋯×ar
ただし、n,l,r はいずれも 1≤l≤r≤n を満たす整数とします。
制約
2≤L≤R≤1018
R−L≤105
1≤M≤106
入力はすべて整数
入力
入力は次の形式で与えられます。
L R M
1 行目には L,R,M がこの順に半角スペース区切りで与えられる
サンプル
サンプル1
入力
2 5 8
出力
4
f(L,R)=n=L∑R((i=1∏ni21)i=1∑n−1(j=1∏i(n−j+1)2j=i+1∏nj2)) として、
g1(n)=i=1∏ni21,g2(n)=i=1∑n−1(j=1∏i(n−j+1)2j=i+1∏nj2),h1(i)=j=1∏i(n−j+1)2,h2(i)=j=i+1∏nj2
とすると、
g2(n)=i=1∑n−1(h1(i)×h2(i))
であり、
f(L,R)=n=L∑R(g1(n)×g2(n))
です。
このとき、f(2,5)=340 であり、これを 8 で割った余りは 4 となります。
サンプル2
入力
2 2 2
出力
0
f(2,2)=4 であり、これは 2 で割り切れます。
サンプル3
入力
999999999999900000 1000000000000000000 1000000
出力
599998
f(L,R) の値は非常に大きくなる可能性があります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。