#P2480. Spoj3105 Mod

    ID: 1535 传统题 1000ms 128MiB 尝试: 1255 已通过: 211 难度: 7 上传者: 标签>CF2200提高+/省选-扩展 BSGSBSGS哈希表快速幂扩展欧几里得算法模逆元鸣谢Hewr

Spoj3105 Mod

题目描述

已知数 a,p,ba,p,b,求满足 ax≡ba^x ≡ b(modmod pp) 的最小自然数 xx。  

输入格式

每个测试文件中最多包含 100100 组测试数据。
每组数据中,每行包含 33 个正整数 a,p,ba,p,b。
当 a=p=b=0a=p=b=0 时,表示测试数据读入完全。  

输出格式

  对于每组数据,输出一行。
如果无解,输出 No Solution,否则输出最小自然数解。  

5 58 33
2 4 3
0 0 0
9
No Solution

数据规模与约定

100%100\% 的数据满足:a,p,b≤1×109a,p,b \le 1 \times 10^9。

提示

2016.3.29 新加数据一组 by  1430586275

题目来源

鸣谢 Hewr