[SDOI 2011]计算器

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

Sample Output

【样例输出1】
2
1
2
【样例输出2】
2
1
0

Hint

【数据规模和约定】
对于100%的数据，1<=y,z,p<=10^9，为质数，1<=T<=10。

题解

数论三合一。

第一问，快速幂。

第二问，扩欧求特解。

第三问，BSGS。

 //It is made by Awson on 2018.1.16

 #include <set>

 #include <map>

 #include <cmath>

 #include <ctime>

 #include <queue>

 #include <stack>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define Abs(a) ((a) < 0 ? (-(a)) : (a))

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))

 using namespace std;

 const LL MOD = ;

 void read(LL &x) {

     char ch; bool flag = ;

     for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || ); ch = getchar());

     for (x = ; isdigit(ch); x = (x<<)+(x<<)+ch-, ch = getchar());

     x *= -*flag;

 }

 void write(LL x) {

     if (x > ) write(x/);

     putchar(x%+);

 }

 LL t, l, a, b, c;

 map<LL, int>mp;

 LL exgcd(LL a, LL b, LL &x, LL &y) {

     if (b == ) {x = , y = ; return a; }

     LL d = exgcd(b, a%b, x, y), t = x;

     x = y, y = t-a/b*y;

     return d;

 }

 LL quick_pow(LL a, LL b, LL c) {

     LL ans = ;

     while (b) {

     if (b&) ans = ans*a%c;

     a = a*a%c, b >>= ;

     }

     return ans;

 }

 LL BSGS(LL a, LL b, LL c) {

     if (b == ) return ;

     if (a ==  && b != ) return -;

     mp.clear();

     LL tim = ceil(sqrt(c)), tmp = b%c;

     for (int i = ; i <= tim; i++) {

     mp[tmp] = i, tmp = tmp*a%c;

     }

     LL t = tmp = quick_pow(a, tim, c);

     for (int i = ; i <= tim; i++) {

     if (mp.count(tmp)) return tim*i-mp[tmp];

     tmp = tmp*t%c;

     }

     return -;

 }

 void work() {

     read(t), read(l);

     while (t--) {

     read(a), read(b), read(c);

     if (l == ) write(quick_pow(a, b, c)), putchar('\n');

     else if (l == ) {

         LL x, y; LL d = exgcd(a, c, x, y);

         if (b%d) printf("Orz, I cannot find x!\n");

         else {x = x*b/d, d = c/d; write((x%d+d)%d), putchar('\n'); }

     }else {

         LL ans = BSGS(a%c, b%c, c);

         if (ans == -) printf("Orz, I cannot find x!\n");

         else write(ans), putchar('\n');

     }

     }

 }

 int main() {

     work();

     return ;

 }

巴特西