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






$ y^x=y^{im-j}\equiv z(mod p)$即$ y^{im} \equiv zy^j (mod p)$
当$ m=\lceil \sqrt{p} \rceil$,且$ i\leq m,j\leq m,i,j\in\mathbb{N}$时
易证:$ { x|x=im-j}={ x|x\leq p \land x \in \mathbb{N} }$
而 $ y^{p-1}\equiv 1(mod\phantom{1} p)$
可以得到:$ {a|a=y^b\phantom{1} mod\phantom{1} p,b \in \mathbb{N} }={ a|a=y^b\phantom{1}mod\phantom{1}p,b\in\mathbb{N}\land b<p-1 }$

所以先枚举j=0~m,算出所有的$ zy^j%p$,存入hash表中。
再枚举i=1~m,算出$ {(z^m)}^i$,如果这个值在hash表中存在,那么((im-j)%(p-1)+p-1)%p-1就是一个答案,取最小值即可。




4 条评论
  1. I have to express appreciation to the writer just for bailing me out of this condition. As a result of surfing throughout the the web and getting concepts which were not helpful, I believed my life was over. Existing without the presence of strategies to the problems you’ve solved by way of the guideline is a critical case, as well as the kind which might have in a negative way damaged my entire career if I had not discovered your website. That capability and kindness in taking care of the whole thing was important. I am not sure what I would’ve done if I hadn’t come across such a thing like this. I can now look ahead to my future. Thanks very much for your reliable and sensible guide. I will not think twice to refer your blog to any person who should have care on this matter.

  2. A lot of thanks for all of your efforts on this web page. Gloria really loves going through research and it is simple to grasp why. All of us notice all of the lively method you give rewarding suggestions via this web site and even increase contribution from other people on this subject so my daughter is always starting to learn a lot. Take pleasure in the remaining portion of the year. You are always conducting a fantastic job.