# BZOJ 2242: [SDOI2011]计算器（快速幂+扩展欧几里得+BSGS）

## Description

1、给定y,z,p,计算Y^Z Mod P 的值；
2、给定y,z,p，计算满足xy≡ Z ( mod P )的最小非负整数；
3、给定y,z,p，计算满足Y^x ≡ Z ( mod P)的最小非负整数。

输入包含多组数据。

【样例输入1】
3 1
2 1 3
2 2 3
2 3 3
【样例输入2】
3 2
2 1 3
2 2 3
2 3 3
【数据规模和约定】

【样例输出1】
2
1
2
【样例输出2】
2
1
0

# BZOJ 3239: Discrete Logging（BSGS模板题）

## Description

Given a prime P, 2 <= P < 231, an integer B, 2 <= B < P, and an integer N, 2 <= N < P, compute the discrete logarithm of N, base B, modulo P. That is, find an integer L such that

## Input

Read several lines of input, each containing P,B,N separated by a space,

## Output

for each line print the logarithm on a separate line. If there are several, print the smallest; if there is none, print “no solution”.

The solution to this problem requires a well known result in number theory that is probably expected of you for Putnam but not ACM competitions. It is Fermat’s theorem that states

for any prime P and some other (fairly rare) numbers known as base-B pseudoprimes. A rarer subset of the base-B pseudoprimes, known as Carmichael numbers, are pseudoprimes for every base between 2 and P-1. A corollary to Fermat’s theorem is that for any m

## Sample Input

5 2 1
5 2 2
5 2 3
5 2 4
5 3 1
5 3 2
5 3 3
5 3 4
5 4 1
5 4 2
5 4 3
5 4 4
12345701 2 1111111
1111111121 65537 1111111111

## Sample Output

0
1
3
2
0
3
1
2
0
no solution
no solution
1
9584351
462803587

i是从1开始枚举，因为害怕出现负数。

# “玲珑杯”1060 — Tetration（指数循环节降幂）

DESCRIPTION

An array b is given, and we can permute the array b into array a.

We want to minimize that interesting expression.

INPUT
The first line is an integer T(1 <= T <= 5), indicating the number of test cases. For each case, the first line contains two integers n, p (1 <= n <= 8, 1 <= p <= 10^9). The second line contains n integers a_i (1 <= a_i <= 10^9),
OUTPUT
Print the result, one per line.
SAMPLE INPUT
1
3 15623
2 3 5
SAMPLE OUTPUT
50