No.1039 Project Euler でやれ

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

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

問題一覧 > 通常問題

No.1039 Project Euler でやれ

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

testestest / テスター :

37zigen

3 ProblemId : 3937 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2020-04-24 18:50:59

ストーリー

yukiさんは次のような問題を作りました。

長さNの数列aが与えられます。
次の2種類のクエリQ個に答えてください。
・1 x y　　 $a_{x}$ を $y$ に変更する ( $0 \leq x < N, 0 \leq y < M$ )
・2 x y　　 $a_{x} + a_{x + 1} + . . . + a_{y} (\mod M)$ を出力する ( $0 \leq x \leq y < N$ )

Binary Indexed Treeを知っていますか？ yukiさんは知っています。
この問題はBinary Indexed Treeを用いて解くことができます。

yukiさんはBinary Indexed Treeが好きです。
ところで、集合と二項演算の組であって、いい感じの条件を満たすものをアーベル群といいます。
(正確な定義はwikipediaを参照してください：アーベル群)
Binary Indexed Treeには一般にアーベル群の構造がのることが知られています。
つまり、集合 ${0, . . ., M - 1}$ が二項演算★によってアーベル群を成すならば、上記問題の2つ目のクエリを

・2 x y　　 $a_{x} ★ a_{x + 1} ★ . . . ★ a_{y}$ を出力する

に置き換えてもBinary Indexed Treeで解くことができます。

問題文

集合

{0, . . ., M - 1}

上の二項演算であって、アーベル群を成すものは何種類存在するでしょうか？　

mod 10^{9} + 7

で答えてください。

入力

$M$

$1 \leq M < 10^{6}$

出力

${0, . . ., M - 1}$ 上の二項演算であって、アーベル群を成すものの個数を $mod 10^{9} + 7$ で出力してください。
最後に改行してください。

サンプル

サンプル1

入力

出力

次の3種類の演算が存在します。
$x ★ y = x + y (\mod 3)$

★	0	1	2
0	0	1	2
1	1	2	0
2	2	0	1

x ★ y = x + y + 1 (\mod 3)

★	0	1	2
0	1	2	0
1	2	0	1
2	0	1	2

x ★ y = x + y + 2 (\mod 3)

★	0	1	2
0	2	0	1
1	0	1	2
2	1	2	0

サンプル2

入力

出力

$x ★ y = x + y + k (\mod 4)$ や $x ★ y = x XOR y XOR k (0 \leq k < 4)$ などの他、次のような謎の演算も条件を満たします。

★	0	1	2	3
0	3	2	0	1
1	2	3	1	0
2	0	1	2	3
3	1	0	3	2

この謎の演算は、例えばpythonで次のように計算されます。
pow(2,pow(3,x,5)+pow(3,y,5)+1,5)%4

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

yukicoder

No.1039 Project Euler でやれ

ストーリー

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力