洛谷 P2485 [SDOI2011]计算器解题报告

P2485 [SDOI2011]计算器

题目描述

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

1、给定y、z、p，计算y^z mod p 的值；

2、给定y、z、p，计算满足xy ≡z(mod p)的最小非负整数x；

3、给定y、z、p，计算满足y^x ≡z(mod p)的最小非负整数x。

为了拿到奖品，全力以赴吧！

输入输出格式

输入格式：

输入文件calc.in 包含多组数据。

第一行包含两个正整数T、K，分别表示数据组数和询问类型（对于一个测试点内的所有数

据，询问类型相同）。

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

输出格式：

输出文件calc.out 包括T 行.

对于每个询问，输出一行答案。

对于询问类型2 和3，如果不存在满足条件的，则输出“Orz, I cannot find x!”。

说明：

T1快速幂

T2逆元orexgcd

无解看看y可不可以整除p

T3 bsgs
从算法竞赛进阶指南上学习的，注意点写了注释

Code:

#include <cstdio>
#include <cmath>
#include <map>
#define ll long long
ll quickpow(ll d,ll k,ll p)
{
    ll f=1;
    while(k)
    {
        if(k&1) f=f*d%p;
        d=d*d%p;
        k>>=1;
    }
    return f;
}
ll work1(ll y,ll z,ll p)
{
    return quickpow(y,z,p);
}
ll work2(ll y,ll z,ll p)//xy=z mod p
{
    if(y%p==0&&z!=0) return -1;
    return z*quickpow(y,p-2,p)%p;
}
std::map <ll,ll > Hash;
ll work3(ll y,ll z,ll p)//y^x=z mod p
{
    Hash.clear();//清空
    z%=p;//注意先取膜
    ll t=sqrt(p)+1;//注意向上取整
    for(ll i=0;i<t;i++)
        Hash[1ll*z*quickpow(y,i,p)%p]=i;
    y=quickpow(y,t,p);//根号次方
    if(y==0) return z==0?1:-1;//特判一下
    for(ll k,j,i=0;i<=t;i++)
    {
        k=quickpow(y,i,p);
        j=Hash.find(k)==Hash.end()?-1:Hash[k];
        if(i*t-j>=0&&~j)//试试 2 2 3这样的情况？
            return i*t-j;
    }
    return -1;
}
int main()
{
    int t,k;
    scanf("%d%d",&t,&k);
    while(t--)
    {
        ll y,z,p;
        scanf("%lld%lld%lld",&y,&z,&p);
        if(k==1) printf("%lld
",work1(y,z,p));
        else if(k==2)
        {
            ll ans=work2(y,z,p);
            if(~ans) printf("%lld
",ans);
            else printf("Orz, I cannot find x!
");
        }
        else
        {
            ll ans=work3(y,z,p);
            if(~ans) printf("%lld
",ans);
            else printf("Orz, I cannot find x!
");
        }
    }
    return 0;
}

2018.9.11