#P16884. SPOJ Power Modulo Inverted。

    ID: 16094 传统题 6000ms 256MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF2100提高+/省选-扩展 BSGSBSGS扩展欧几里得算法模逆元快速幂哈希表

SPOJ Power Modulo Inverted。

题目描述

给定三个正整数 x,y,zx,y,z,利用快速幂可以很容易计算

k=xy mod z.k=x^y\bmod z.

现在要求解决它的“逆问题”。

给定正整数 x,z,kx,z,k,求最小的非负整数 yy,满足

xy≡k(modz).x^y\equiv k\pmod z.

如果不存在这样的 yy,则输出 No Solution。

注意:zz 不保证是质数,xx 与 zz 也 不保证互质。

输入格式

每组一行三个整数 x,z,kx,z,k。

当读到

0 0 0

时输入结束,该行不需要处理。

输出格式

对于每组测试用例:

  • 如果存在解,输出满足条件的最小非负整数 yy;
  • 否则输出 No Solution。

数据范围

1≤x,z,k≤109.1\le x,z,k\le 10^9.

样例

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