OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【SDOI2011】计算器

【题目描述】

你被要求设计一个计算器完成以下三项任务:

1、给定y、z、p,计算y^z mod p的值;

2、给定y、z、p,计算满足xy mod p=z 的最小非负整数x;

3、给定y、z、p,计算满足y^x mod p=z的最小非负整数x。

【输入】

输入包含多组数据。

第一行包含两个正整数 T、L,分别表示数据组数和询问类型(对于一个测试点内的所有数据,询问类型相同)。

以下T行每行包含三个正整数y、z、p,描述一个询问。

【输出】

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

【输入样例】

【task1】

3 1

2 1 3

2 2 3

2 3 3

【task2】

3 2

2 1 3

2 2 3

2 3 3

【task3】

4 3

2 1 3

2 2 3

2 3 3

2 4 3

【输出样例】

【task1】

2

1

2

【task2】

2

1

0

【task3】

0

1

Orz, I cannot find x!

0

【数据范围】

对于100%的数据,1≤y,z,p≤10^9,P为质数,1≤T≤10。

【题解】

task1是快速幂,b^p=(b^p/2)^2*(b^p%2),多取模几次总是不会错的。

task2是扩展欧几里德算法,根据题意化简方程得x*y+t*p=z,要求解出最小的x。当z%gcd(y,p)≠0时无解,否则先exgcd解x*y+t*p=1,然后把x扩大z倍。此时x可能是负数,一直加p/gcd(y,p)直到为正即可。具体证明请询问度娘。x∈[0,p-1]。所以我们先枚举x∈[0,m-1],储存所有y^x%p,如果存在

task3需要分块。根据题意化简方程得y^x≡z(mod p),由费马小定理可得,如果方程有解,则∃x∈[0,p-1]。所以我们先枚举x∈[0,m-1],储存所有y^x%p,如果其中一个的值等于z就找到了,如果没有,接下来应该枚举x∈[m,m*2-1],等于把原来储存的值乘上y^m,利用乘法逆元,等价于z乘上y^(-m),所以不必再枚举了。

关于m的取值,最优是√p,时间复杂度是这么计算的:第一次枚举+快速幂需要O(mlogm),以后每一次乘上y^m需要O(logm),一共要乘p/m次,所以时间复杂度为O((m+p/m)logm),当m接近√p时,复杂度最低为O(√plogp)。

【代码】

和蔼可亲的质数p,否则貌似要OTL中国剩余定理QAQ

http://paste.ubuntu.com/7203056/

评论

© OI技术宅 | Powered by LOFTER