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

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

Solution

典型的NOIP三合一题,硬是把三道题合在了一起……
前两问就不说了(一个快速幂,一个exgcd)……

而要怎么解决第三问呢?
要用到BSGS(Baby-Step-Giant-Step)算法。用某方姓大佬的话:

就是枚举到根号的暴力

设x=im-j
$ 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就是一个答案,取最小值即可。

Code

代码跑得好慢,我好菜啊。

#include<cstdio>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
typedef long long ll;
map<ll,ll>Map;
ll ksm(ll a,ll b,ll mo1)
{
    ll ans=1,tmp=a%mo1;
    while (b)
    {
        if (b&1) ans=ans*tmp%mo1;
        tmp=tmp*tmp%mo1; 
        b>>=1;
    }
    return ans;
}
ll exgcd(ll n,ll m,ll &x,ll &y)
{
    if (!m) 
    {
        x=1,y=0;
        return n;
    }
    ll g=exgcd(m,n%m,x,y);
    ll t=x;
    x=y,y=t-n/m*y;
    return g;
}
int main()
{
    int cas,type;
    scanf("%d%d",&cas,&type);
    while (cas--)
    {
        ll a,b,p;
        scanf("%lld%lld%lld",&a,&b,&p);
        if (type==1)
        {
            printf("%lld\n",ksm(a,b,p));
        }
        if (type==2)
        {
            ll x,y;
            ll g=exgcd(a,p,x,y);
            if (b%g)
            {
                puts("Orz, I cannot find x!");
                continue;
            }
            a/=g,b/=g,p/=g;
            exgcd(a,p,x,y);
            x=(x%p+p)%p;
            x=x*b%p;
            printf("%lld\n",x);
        }
        if (type==3)
        {
            if (a%p==0) 
            {
                if (b%p==0) puts("1");
                else if (b%p==1) puts("0");
                else puts("Orz, I cannot find x!");
                continue;
            }
            Map.clear();
            int m=sqrt(p)+1;
            ll xx=1;
            Map[b%p]=1;
            for (int i=1;i<=m;i++)
            {
                (xx*=a)%=p;
                Map[xx*b%p]=i+1;
            }
            xx=ksm(a,m,p);
            ll x1=1,ans=1LL<<50;
            for (int i=1;i<=m;i++)
            {
                (x1*=xx)%=p;
                if (Map[x1])
                {
                    ans=min(ans,(((ll)i*m-Map[x1]+1)%(p-1)+(p-1))%(p-1));
                }
            }
            if (ans<p) printf("%lld\n",ans);
            else puts("Orz, I cannot find x!");
        }
    }
    return 0;
}

 

4 thoughts on “BZOJ2242 计算器”

  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.

Leave a Comment

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