/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
x を m で割った余りを f(x,m) と表します。
初期値 A_1=X および漸化式 A_{n+1}= f(A_n^2, M) で定まる数列を A とします。\displaystyle{\sum_{i=1}^N A_i} を求めてください。
制約
- 1 \leq N \leq 10^{10}
- 0 \leq X < M \leq 10^5
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N X M
出力
\displaystyle{\sum_{i=1}^N A_i} を出力せよ。
入力例 1
6 2 1001
出力例 1
1369
数列 A は 2,4,16,256,471,620,\ldots となるので、答えは 2+4+16+256+471+620=1369 となります。
入力例 2
1000 2 16
出力例 2
6
数列 A は 2,4,0,0,\ldots となるので、答えは 6 となります。
入力例 3
10000000000 10 99959
出力例 3
492443256176507
Score : 500 points
Problem Statement
Let us denote by f(x, m) the remainder of the Euclidean division of x by m.
Let A be the sequence that is defined by the initial value A_1=X and the recurrence relation A_{n+1} = f(A_n^2, M). Find \displaystyle{\sum_{i=1}^N A_i}.
Constraints
- 1 \leq N \leq 10^{10}
- 0 \leq X < M \leq 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X M
Output
Print \displaystyle{\sum_{i=1}^N A_i}.
Sample Input 1
6 2 1001
Sample Output 1
1369
The sequence A begins 2,4,16,256,471,620,\ldots Therefore, the answer is 2+4+16+256+471+620=1369.
Sample Input 2
1000 2 16
Sample Output 2
6
The sequence A begins 2,4,0,0,\ldots Therefore, the answer is 6.
Sample Input 3
10000000000 10 99959
Sample Output 3
492443256176507