BZOJ2330/SDOI2011/计算器

Posted on By 二价氢

#题目描述

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

  1. 给定\(y,z,p\),计算\(y^z \mathrm{mod} P\) 的值;
  2. 给定\(y,z,p\),计算满足\(xy\equiv Z ( \mathrm{mod}\ P )\)的最小非负整数;
  3. 给定\(y,z,p\),计算满足\(y^x\equiv Z ( \mathrm{mod}\ P )\)的最小非负整数。

#做法

  1. 不会的话可以退役了
  2. 不会的话可以退役了
  3. Baby Step,Giant Step

#复杂度分析

N/A

#AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
struct Op1{
    long long y,z,p;
    long long Pow()
    {
        long long ret=1;
        for (;z;(y*=y)%=p,z>>=1)
            if (z&1)
                (ret*=y)%=p;
        return ret;
    }
    void work()
    {
        scanf("%lld%lld%lld",&y,&z,&p);
        printf("%lld\n",Pow());
    }
};
struct Op2{
    long long y,z,p;
    long long aa,bb;
    long long ext_gcd(long long a,long long b)
    {
        if (b==0)
        {
            aa=1;bb=1;
            return a;
        }
        long long tt=ext_gcd(b,a%b);
        long long t=aa;
        aa=bb;
        bb=t-a/b*bb;
        return tt;
    }
    void work()
    {
        scanf("%lld%lld%lld",&y,&z,&p);
        long long d=ext_gcd(y,p);
        if (z%d)
        {
            printf("Orz, I cannot find x!\n");
            return;
        }
        aa=aa*z/d;
        aa=(aa+p)%p;
        while (aa<0)
            aa+=p;
        printf("%lld\n",aa);
    }
};
struct Op3{
    long long y,z,p;
    long long Pow(long long x,long long pp)
    {
        long long ret=1;
        for (;pp;(x*=x)%=p,pp>>=1)
            if (pp&1)
                (ret*=x)%=p;
        return ret;
    }
    long long Work()
    {
        y%=p;z%=p;
        if (!y && !z)
            return 1;
        if (!y)
            return -1;
        map<long long,long long> hash;
        long long m,v,e=1;
        m=ceil(sqrt(p+0.5));
        v=Pow(y,p-m-1);
        hash[1]=m;
        for (int i=1;i<m;i++)
        {
            (e*=y)%=p;
            if (!hash[e])
                hash[e]=i;
        }
        for (int i=0;i<m;i++)
        {
            if (hash[z])
            {
                long long num=hash[z];
                hash.clear();
                return i*m+(num==m?0:num);
            }
            (z*=v)%=p;
        }
        return -1;
    }
    void work()
    {
        scanf("%lld%lld%lld",&y,&z,&p);
        long long ans=Work();
        if (ans!=-1)
            printf("%lld\n",ans);
        else
            printf("Orz, I cannot find x!\n");
    }
};
int main()
{
    Op1 a;Op2 b;Op3 c;
    int t,k;
    scanf("%d%d",&t,&k);
    if (k==1)
        while (t--)
            a.work();
    if (k==2)
        while (t--)
            b.work();
    if (k==3)
        while (t--)
            c.work();
    return 0;
}