题目描述
给定正整数 a, c, p,保证 p 是素数,求 b 使得:
ab≡bc(modp)
我们称整数 A,B,C 有 A≡B(modC),当且仅当存在整数 k 使得 A−B=C×k。
输入格式
输入仅一行三个整数 a, c 和 p (1≤a,c<p≤109),由一个空格隔开,含义如题面所述。
数据保证 p 是素数。
输出格式
输出仅一个整数 b (1≤b≤1018),如果有多个合法答案,你可以输出任意一个。
可以证明,在范围内至少存在一个解。
3 5 7
16
14530529 19260817 19491001
5660025
提示
对于第一组样例,我们有:
316≡165(mod7)
因为:
316mod7=43046721mod7=4
165mod7=1048576mod7=4