#1706. [语言月赛 202501] Pollard-Rho

[语言月赛 202501] Pollard-Rho

题目描述

小 Y 家有一个智能密码锁,密码是 0∼99990\sim 9999 的一个整数。这个密码锁和一般密码锁不同之处在于,假设当前密码为 xx,用这个密码开一次门之后,密码就会变成 x2+Cx^2+C 除以 1000010000 的余数,其中 CC 是用户设定好,不会发生改变的数值。

现在小 Y 忘记自己家的密码了,只记得初始密码 x1x_1 和设置的 CC,以及这是他第 kk 次开门,请帮他计算这次开门的密码。

输入格式

输入一行三个正整数 x1,C,kx_1,C,k,表示初始密码、设置的 CC,以及这是第几次开门。

输出格式

输出一行一个自然数,表示这一次开门的密码。

样例

1000 3 1
1000
1000 3 2
3
1000 3 3
12

题目来源:洛谷 B4122