#P3285. Gift

    ID: 2472 传统题 1000ms 512MiB 尝试: 110 已通过: 35 难度: 6 上传者: 标签>难度分类提高数论BSGS费马小定理模逆元快速幂同余的加减乘运算CF2100

Gift

题目描述

小时候,tangjz 收到 simoncao 送来的一件礼物,里面有许多题目。其中一道题要求求出满足

gaX+b≡c(modp)g^{aX+b}\equiv c\pmod p

的最小正整数 XX。保证 pp 是质数。

输入格式

从标准输入读入数据。一行五个由空格分隔的正整数 a,b,c,g,pa,b,c,g,p。

输出格式

向标准输出写入结果。若有解,则输出最小的正整数 XX。若无解,则输出 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)3^{1\cdot 1+2}=27\equiv6\pmod 7。

第二组中,41,42,43,444^1,4^2,4^3,4^4 对 77 取模依次为 4,2,1,44,2,1,4。此后循环,无法得到 66。

数据范围

数据比例 范围
30%30\% a,b,c,g≤103a,b,c,g\le 10^3
60%60\% a,b,c,g,p≤107a,b,c,g,p\le 10^7
100%100\% a,b,c,g≤101000000a,b,c,g\le 10^{1000000},p<231p<2^{31}

原题面 PDF