No.1262 Let's Make a Graph!
タグ : / 解いたユーザー数 43
作問者 :
PCTprobability
/ テスター :
nok0
Problem Statement
You are given positive integers $N,M$ and a sequence of positive numbers $A$ of length $M$.
We define the function $f(a, b)$ as follows.
Prepare $N$ vertices numbered $0,1,...,N-1$, and let the variables be $X:=a-1, Y:=(X-b)mod\ a$. Then perform the following operations.
- Add a directed edge from vertex $X$ to vertex $Y$.
- Set $X=Y$, $Y=(Y-b)mod\ a$.
- If there exists a cycle whose start and end point is vertex $a-1$, define $f(a,b) = $ the minimum vertex number contained in the cycle, and terminate the operations.
- Here, the cycle is taken to be a simple cycle, and it is guaranteed that such a cycle is determined in exactly $1$ way. (Added at 21:52) Otherwise, repeat the operations from the beginning.
Find $\sum_{i = 0}^{M-1}\sum_{j = 1}^{A_i}f(A_i,j)$.
Input
$N$ $M$
$A_0$ $A_1$ ...$A_{M-1}$
・All inputs are integers.
・$1 \le N,M \le 10^6$
・$1 \le A_i \le N$
Output
Find $\sum_{i = 0}^{M-1}\sum_{j = 1}^{A_i}f(A_i,j)$. Print a newline at the end.
Sample
Sample 1
Input
3 1
3
Output
2
We find $f(3,1)+f(3,2)+f(3,3)$. Consider $f(3,1)$.
- Initially, $x=2,y=1$. Here, we connect vertex $2$ and vertex $1$. There is no cycle yet whose start and end point is vertex $2$, so we continue the operations.
- Now $x=1,y=0$. We connect vertex $1$ and vertex $0$. There is no cycle yet whose start and end point is vertex $2$, so we continue the operations.
- Now $x=0,y=2$. We connect vertex $0$ and vertex $2$. Here, a cycle whose start and end point is vertex $2$ is formed, and the minimum vertex number contained in that cycle is $0$, so $f(3,1)=0$.
Sample 2
Input
100 5
23 34 54 99 57
Output
746
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。