题目描述
小时候,tangjz 收到 simoncao 送来的一件礼物,里面有许多题目。其中一道题要求求出满足
gaX+b≡c(modp)
的最小正整数 X。保证 p 是质数。
输入格式
从标准输入读入数据。一行五个由空格分隔的正整数 a,b,c,g,p。
输出格式
向标准输出写入结果。若有解,则输出最小的正整数 X。若无解,则输出 no solution。
样例 1
1 2 6 3 7
1
样例 2
1 2 6 4 7
no solution
样例 3
605292043 519693731 696695585 716945560 2012182013
18302194
样例解释
第一组中,31⋅1+2=27≡6(mod7)。
第二组中,41,42,43,44 对 7 取模依次为 4,2,1,4。此后循环,无法得到 6。
数据范围
| 数据比例 |
范围 |
| 30% |
a,b,c,g≤103 |
| 60% |
a,b,c,g,p≤107 |
| 100% |
a,b,c,g≤101000000,p<231 |
原题面 PDF