[Login|Register]
Problems

Status

Rank

Problem 1403
萌萌的萌
Time Limit: 10000ms
Memory Limit: 262144kb
Description
某天,萌萌发现自己的萌居然可以当成食物!不过,为了避免暴饮暴食带来的一系列后果,萌萌决定提前规划一下他的萌。
萌萌的萌每天都在按照某个规律增长,若第i天萌萌有x[i]单位的萌,那么第i+1天他就会有x[i+1] = a*x[i]+b单位的萌,其中a、b为给定常数。萌萌知道指数增长的可怕性,于是乎当萌超过9999677时,他会把多出去的部分吃掉。这样萌萌在每一天结束时所剩的萌满足
x[i+1] = (a*x[i]+b) mod 9999677
萌萌第一天有x[1] = b单位的萌,现在他想知道,最短需要多少天,他的萌能正好达到M
Input
多组数据,以-1 -1 -1为结尾
每组数据占一行,包含三个正整数依次为M、a、b
注意正整数不包括0
a、b、M<9999677
数据保证 a!=1 且一定有解
数据组数不超过10000
Output
对每组输入数据,输出一个正整数n,且n为满足x[n] = M的所有正整数中最小的正整数
Sample Input
7 2 1
15 2 1
80 3 2
4 10800 4
-1 -1 -1
Sample Output
3
4
4
1
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 2.4ms with 1 query(s).