题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2242
数据生成器：http://paste.ubuntu.com/22875643/
数据传送门：http://pan.baidu.com/s/1dE71QHr
这个题，做了一个下午+一个晚上，最后才发现是把”cannot”中间多加了一个‘a’
MD，老子好想杀人！ (╯‵□′)╯︵┻━┻
题目本身很简单，就是快速幂+拓展欧几里得+BSGS
但网上的程序，多少有问题，反正我能搜出来的，我都可以叉掉
我这份代码问题应该比较少吧：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define LL long long
using namespace std;
const int MAXN = 100000;
const double EPS = 1e-5;
namespace Hash{
const int MOD = 99971;
int head[MAXN],nxt[MAXN],val[MAXN],data[MAXN],T;
inline void init(){
T = 0;
memset(head,0,sizeof(head));
}
inline void insert(int w, int d){
nxt[++T] = head[w%MOD];
val[T] = w; data[T] = d;
head[w%MOD] = T;
}
inline int find(int w){
for (int i=head[w%MOD];i;i=nxt[i])
if (val[i] == w) return data[i];
return -1;
}
};
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline int quick_pow(int a,int b,int c){
int ret = 1; while (b) {
if (b & 1) ret = ((LL)ret * a) % c;
a = (LL)a*a%c; b >>= 1;
} return ret;
}
int GCD(int a, int b){return b?GCD(b,a%b):a;}
void EX_GCD(int a, int b, int &x, int &y){
if (!b) x=1, y=0;
else EX_GCD(b,a%b,y,x), y-=a/b*x;
}
inline int EX_GCD(int a, int b, int c) {
int ret,tmp,gcd=GCD(a,b);
if (c%gcd) return -1;
else {
EX_GCD(a/gcd,b/gcd,ret,tmp);
ret = (((LL)c/gcd*ret) % b + b) % b;
return ret;
}
}
inline void solve(int a, int b, int c) {
int ret = EX_GCD(a,c,b);
if (~ret) printf("%d\n",ret);
else printf("Orz, I cannot find x!\n");
}
inline void BSGS(int a, int b, int c) {
Hash::init(); a %= c; b %= c;
if (!a && b > 1) {printf("Orz, I cannot find x!\n"); return;}
int lim = int(ceil(sqrt(c))+EPS);
for (int i=0,w=1;i<=lim;i++) {
if (w == b) {printf("%d\n",i); return;}
Hash::insert(w,i);
w = ((LL)w*a) % c;
}
int w_ori = quick_pow(a,lim,c), rev_ori = quick_pow(w_ori,c-2,c);
for (int i=1,w=w_ori,rev=rev_ori;i<=lim;i++) {
int tmp = Hash::find(((LL)rev*b) % c);
if (tmp > -1) {printf("%d\n",i*lim+tmp); return;}
w = ((LL)w*w_ori) % c;
rev = ((LL)rev*rev_ori) % c;
}
printf("Orz, I cannot find x!\n");
}
int main(){
int T=read(),ty=read(); while (T--) {
int a=read(), b=read(), c=read();
if (ty == 1) printf("%d\n",quick_pow(a,b,c));
else if (ty == 2) solve(a,b,c);
else BSGS(a,b,c);
}
return 0;
}
