蒟蒻求助80分
查看原帖
蒟蒻求助80分
183023
jackson303楼主2021/7/22 20:23

麻烦各位大佬帮我康康哪里错了?

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include<bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds;
int log_mod(int a,int b,int n) {
	if (b==1) return 0;
	gp_hash_table<int,int>hash;
	int t=ceil(sqrt(n));
	long long z=1;
	for (int i=0; i<t; i++) {
		hash[b*z%n]=i;
		z=z*a%n;
	}
	int now=1;
	for (int i=1; i<=t; i++) {
		now=now*z%n;
		if (hash.find(now)!=hash.end()) {
			return i*t-hash[now];
		}
	}
	return -1;
}
long long exgcd(long long a,long long b,long long &x,long long &y) {
	if (b==0) {
		x=1;
		y=0;
		return a;
	}
	long long d=exgcd(b,a%b,x,y);
	long long t=x;
	x=y;
	y=t-a/b*y;
	return d;
}
long long solve(long long a,long long b,long long c) {
	long long x,y;
	long long d=exgcd(a,b,x,y);
	if(c%d!=0)return -1;
	x*=(c/d);
	long long tb=abs(b/d);
	return (x%tb+tb)%tb;
}
long long pmod(long long a,long long b,long long k) {
	long long r=1;
	while(b) {
		if(b&1) r=(r*a)%k;
		b>>=1;
		a=(a*a)%k;
	}
	return r;
}
int main() {
	long long t,k;
	cin>>t>>k;
	while(t--) {
		long long y,z,p;
		cin>>y>>z>>p;
		if(k==1)cout<<pmod(y,z,p)<<endl;
		if(k==2) {
			int ans=solve(y,p,z);
			if(ans!=-1)cout<<ans<<endl;
			else cout<<"Orz, I cannot find x!"<<endl;
		}
		if(k==3) {
			long long ans=log_mod(y,p,z);
			if(ans!=-1)cout<<ans<<endl;
			else cout<<"Orz, I cannot find x!"<<endl;
		}
	}
}
2021/7/22 20:23
加载中...