月度归档:2016年12月

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)的最小非负整数。

Input

 输入包含多组数据。

第一行包含两个正整数T,K分别表示数据组数和询问类型(对于一个测试点内的所有数据,询问类型相同)。
以下行每行包含三个正整数y,z,p,描述一个询问。

Output

对于每个询问,输出一行答案。对于询问类型2和3,如果不存在满足条件的,则输出“Orz, I cannot find x!”,注意逗号与“I”之间有一个空格。

Sample Input

【样例输入1】
3 1
2 1 3
2 2 3
2 3 3
【样例输入2】
3 2
2 1 3
2 2 3
2 3 3
【数据规模和约定】
对于100%的数据,1<=y,z,p<=10^9,p为质数,1<=T<=10。

Sample Output

【样例输出1】
2
1
2
【样例输出2】
2
1
0
操作1:就是快速幂。
操作2:发现,等价于,那么这很明显是个扩欧的式子了,突然发现自己的扩欧板子好垃圾,找别人扒了一份。以后就当做模板好了。。。注意把p取负。
操作3:BSGS,然后发现自己之前的没有判断A是p的倍数的情况。

 

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

一直不是很懂数论中的一些基本知识。。。所以赶快学了一下BSGS算法。额,我还不会扩展版本,所以先说一下普通的BSGS。
首先题目给出了这样一个式子。C是质数,并且认为。因为若C为质数且A,C不互质那么肯定A是C的倍数,所以除非B是0否则一直无解,这些细节是可以特判掉的。
我们做一步转换,那么.我们从0-m枚举j,得出的存入到一个hash表内(也可以用map,但是实测发现map实在是有点慢)。这就是我们说的小步。
然后枚举i,从1到p/m,如果发现计算的有在hash表内对应的,那么就返回答案,即找到一个最小值。复杂度是O(m+p/m),所以取.
说几点注意事项:
i是从1开始枚举,因为害怕出现负数。
因为,所以当出现不同的j得到了相同的,我们用较大的j替代。
那么这个题就是一个BSGS的模板题了。。。抄了clearY的hash表。

 

“玲珑杯”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
很早之前打得一场比赛,因为大佬都去CCPC final了,所以这场打到了rk17.但是还是没拿到钱。。。这个题目当时数据水了,所以我没考虑一种情况也能AC,今天补了。
首先发现这个式子就是通过指数循环节降幂公式:进行递推,我们需要求出的是phi(p),phi(phi(p))…..然后从后向前递推快速幂计算出来答案即可。当时没有考虑phi(b)>x的情况。其实把代码改一改,在快速幂的计算工程中判断一下答案是否超过了mod,超过了就说明原来的x肯定是大于b的。反之这说明x一直小于b,那么我们最后就不要加上那个mod就好啦。