2374 - 编号机

题目描述

A 工厂的编号机,专门产生数字,用于给工厂的各类设备编号。

大家都知道,既然是用于给设备编号,那么这个编号机产生的数字一定要保证唯一性。

该编号机产生数字的方式如下。如果要产生一个数列 {a_0,a_1 \dots a_n},则先指定 a_0=1,其余数字的生成方式为:ai+1=(A \times a_i + a_i \mod B) \mod C

请编程校验一下,该数字机是否有可能产生出重复的数字,如果可能产生重复的数字,请输出第 1 个产生重复数字的编号(请注意,第 1 个产生的数字编号为 0)。

由于工厂的设备不可能超过 2 \times 10^6 台,因此只要产生的前 2 \times 10^6 个数字中无重复,就可以认为不会产生重复的数字,输出 -1

输入

输入 3 个整数 A,B,C

输出

按要求输出第 1 个重复数字的编号 或者 -1

样例

输入

2 2 9

输出

4 
说明

数据范围

对于 30\% 的数据 A,B,C≤10^5

对于 100\% 的数据 A,B,C≤10^9

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 入门


上一题 下一题