No.1039 Do It on Project Euler
タグ : / 解いたユーザー数 15
作問者 :
testestest
/ テスター :
37zigen
Story
yuki created the following problem.
You are given a sequence a of length N.
Answer Q queries of the following two types.
・1 x y Change $a_x$ to $y$ ($0 \leq x < N,\ \ 0\leq y < M$)
・2 x y Output $a_x + a_{x+1} + ... + a_y \pmod M$ ($0\leq x \leq y < N$)
Do you know the Binary Indexed Tree? yuki does.
This problem can be solved using a Binary Indexed Tree.
yuki likes Binary Indexed Trees.
By the way, a pair of a set and a binary operation satisfying certain nice conditions is called an abelian group.
(For the precise definition, see Wikipedia: Abelian group)
It is known that, in general, a Binary Indexed Tree can carry the structure of an abelian group.
That is, if the set $\{0,...,M-1\}$ forms an abelian group under a binary operation ★, then the second query of the above problem can be replaced with
・2 x y Output $a_x ★ a_{x+1} ★ ... ★ a_y$and the problem can still be solved with a Binary Indexed Tree.
Problem Statement
How many binary operations on the set $\{0,...,M-1\}$ form an abelian group? Answer $\bmod 10^9+7$.Input
$M$
$1\leq M < 10^6$
Output
Output the number of binary operations on $\{0,...,M-1\}$ that form an abelian group, $\bmod 10^9+7$.
Print a newline at the end.
Sample
Sample 1
Input
3
Output
3
The following 3 operations exist.
$x ★ y = x+y \pmod 3$
| ★ | 0 | 1 | 2 |
| 0 | 0 | 1 | 2 |
| 1 | 1 | 2 | 0 |
| 2 | 2 | 0 | 1 |
$x ★ y = x+y+1 \pmod 3$
| ★ | 0 | 1 | 2 |
| 0 | 1 | 2 | 0 |
| 1 | 2 | 0 | 1 |
| 2 | 0 | 1 | 2 |
$x ★ y = x+y +2\pmod 3$
| ★ | 0 | 1 | 2 |
| 0 | 2 | 0 | 1 |
| 1 | 0 | 1 | 2 |
| 2 | 1 | 2 | 0 |
Sample 2
Input
4
Output
16
Besides operations such as $x ★ y = x+y+k \pmod 4$ and $x ★ y = x \ \mbox{XOR}\ y\ \mbox{XOR} \ k\ (0\leq k < 4)$, mysterious operations like the following also satisfy the condition.
| ★ | 0 | 1 | 2 | 3 |
| 0 | 3 | 2 | 0 | 1 |
| 1 | 2 | 3 | 1 | 0 |
| 2 | 0 | 1 | 2 | 3 |
| 3 | 1 | 0 | 3 | 2 |
This mysterious operation can be computed, for example, in python as follows.
pow(2,pow(3,x,5)+pow(3,y,5)+1,5)%4
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。