#P1467. Pku3243 clever Y

    ID: 479 传统题 1000ms 512MiB 尝试: 498 已通过: 184 难度: 7 上传者: 标签>CF2200提高+/省选-扩展 BSGSBSGS哈希表模逆元扩展欧几里得算法快速幂ghy

Pku3243 clever Y

题目描述

小Y发现,数学中有一个很有趣的式子:

XY mod Z=KX^Y \bmod Z = K

给出 X、Y、ZX、Y、Z,我们都知道如何很快的计算 KK。但是如果给出 X、Z、KX、Z、K,你是否知道如何快速的计算 YY 呢?

输入格式

本题由多组数据(不超过 2020 组),每组测试数据包含一行三个整数X、Z、KX、Z、K(0≤X,Z,K≤1090\leq X, Z, K\leq 10^9)。 输入文件一行由三个空格隔开的 00 结尾。

输出格式

对于每组数据:如果无解则输出一行 No Solution,否则输出一行一个整数 Y(0≤Y<Z)Y(0 \leq Y < Z),使得其满足 XY mod Z=KX^Y \bmod Z = K,如果有多个解输出最小的一个 YY。

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

题目来源

ghy

本站边界约定

终止行 0 0 00\ 0\ 0 不处理。对于其他数据,必须在 0≤Y<Z0\le Y<Z 中寻找答案;若 Z=0Z=0,该候选范围为空,输出 No Solution。当 Z>0Z>0 时按非负整数模幂计算,约定 X0=1X^0=1(包括 X=0X=0),再对 ZZ 取模。输入的 KK 是指定余数,因此若 K≥ZK\ge Z,没有符合条件的 YY。