[BZOJ2242] 计算器题解

Description

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

输入包含多组数据。

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

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

【样例输入1】

3 1

2 1 3

2 2 3

2 3 3

【样例输入2】

3 2

2 1 3

2 2 3

2 3 3

【数据规模和约定】

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

【样例输出1】

【样例输出2】

思路:将本题的3个任务拆分来看,任务1就是快速幂模板,任务2就是用exgcd求解不定方程,任务3就是 Baby Step Giant Step求解高次同余方程.那么3个模板凑在一起分别操作即可

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <map>
using namespace std;
#define rg register
#define LL long long
#define __space putchar(' ')
#define __endl putchar('\n')
#define debug printf("Time Test:%d\n",clock())
template <typename qwq> inline void read(qwq & x)
{
    x = 0;
    rg int f = 1;
    rg char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    x *= f;
}
template <typename qaq> inline void print(qaq x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
int p;
inline LL Pow(LL x,LL y)
{
    rg LL ret = 1;
    while(y)
    {
        if (y & 1) ret = ret * x % p;
        x = x * x % p;
        y >>= 1;
    }
    return ret % p;
}
inline LL exgcd(LL a,LL b,LL & x,LL & y)
{
    if (!b)
    {
        x = 1,y = 0;
        return a;
    }
    rg LL temp = exgcd(b,a % b,x,y);
    rg LL t = x;
    x = y;
    y = t - a / b * y;
    return temp;
}
map<int,int> hash;
inline int Baby_Step_Giant_Step(int a,int b)
{
    hash.clear();
    b %= p;
    rg int t = ceil(sqrt(p));
    for (rg int j = 0; j < t; ++j)
    {
        rg int val = (LL) b * Pow(a,j) % p; //b * a ^ j;
        hash[val] = j;
    }
    a = Pow(a,t); //a ^ t
    if (!a) return !b ? 1 : -1;
    for (rg int i = 0; i <= t; ++i)
    {
        rg int val = Pow(a,i); //(a ^ t) ^ i
        rg int j = hash.find(val) == hash.end() ? -1 : hash[val];
        if (j >= 0 && i * t - j >= 0) return i * t - j;
    }
    return -1;
}
int t,k,y,z;
LL xx,yy;
inline void work1()
{
    print(Pow(y,z)),__endl;
    return;
}
inline void work2()
{
    rg LL gcd = exgcd(y,p,xx,yy);
    if (z % gcd)
    {
        puts("Orz, I cannot find x!");
        return;
    }
    rg LL temp = p / gcd;
    while (xx < 0) xx += temp;
    print(((xx * z / gcd) % temp + temp) % temp),__endl;
}
inline void work3()
{
    rg LL ans = Baby_Step_Giant_Step(y,z);
    if (ans == -1 ) puts("Orz, I cannot find x!");
    else print(ans),__endl;
    return;
}
int main()
{
    read(t),read(k);
    while (t--)
    {
        read(y),read(z),read(p);
        switch (k)
        {
            case 1:
                work1();
                break;
            case 2:
                work2();
                break;
            case 3:
                work3();
                break;
        }
    }
    return 0;
}

[BZOJ2242] 计算器 题解

[BZOJ2242] 计算器题解