stdKonjac's Blog

An AC a day keeps the WA away ~

【SDOI2011 计算器】

题目来源:

bzoj2242

题目描述:

你被要求设计一个计算器完成以下三项任务:
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)的最小非负整数。

输入格式

 输入包含多组数据。

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

输出格式

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

样例数据1

输入

3 1

2 1 3

2 2 3

2 3 3

输出

2

1

2

样例数据2

输入

3 2

2 1 3

2 2 3

2 3 3

输出

2

1

0

【数据规模和约定】


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

Baby Step Giant Step模板题。

我发现我数论完蛋了……这道题搞了1个下午+1个晚上才艰难的搞出来,主要是推方程推了好久……最后总算是搞明白原理了。下面是我的推导过程:

首先,让我们搞清楚一个概念:“模P意义下的除法” 它的意思是:P是质数时  A/B≡A*B^(P-2) (mod P) 至于这个意义是怎么来的我也不明白,改日问问LLX大神好了。

然后就是推方程了,这里直接写:

y^x≡z(mod p)

y^(km+i)≡z(mod p)

y^i≡z/(y^km) (mod p)

y^i≡z*y^km^(p-2)) (mod p)

就是这几个蛋疼的方程,主要是那个概念忘记了于是死活推不出来方程啊我去!接下来就简单了,对于每个问题:

Q1: 快速幂即可 。

Q2 :稍微变一下形用扩展欧几里得即可。

Q3 :用刚才的方程,把x分解为km+i再算,其中y^i可以预先存map构造的hash表里(不嫌麻烦也可以手写,反正我哈希表手写是挂掉了,但是手写速度的确快)。

下面是代码:

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.