目录
BZOJ2242 计算器题解ｃｏｄｅ
BZOJ2242 计算器
题目传送门
题解
一道比较模板的题目，第一个操作暴力快速幂搞，第二个操作暴力\(Exgcd\)搞，第三个操作暴力\(BSGS\)搞。注意判无解的情况就行了。
ｃｏｄｅ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
ll y,z,p;
std::map<ll,ll>Mp;
int T,k;
/*==================Define Area================*/
ll Powe(ll x,ll y,ll p) {
ll res=1;
while(y) {
if(y&1) res*=x,res%=p;
x*=x;x%=p;
y>>=1;
}
return res;
}
void Exgcd(ll a,ll b,ll &x,ll &y) {
if(!b) {
x=1,y=0;
return ;
}
Exgcd(b,a%b,x,y);
ll t=x;x=y;y=t-a/b*y;
}
ll Gcd(ll x,ll y) {
if(!y) return x;
else return Gcd(y,x%y);
}
void Solve1(ll a,ll b,ll c) {
ll ans=Powe(a,b,c);
printf("%lld\n",ans);
return ;
}
void Solve2(ll a,ll b,ll c) {
c=-c;
ll G=Gcd(a,c);
if(b%G!=0) {
puts("Orz, I cannot find x!");
return ;
}
a/=G;b/=G;c/=G;
ll x,y;
Exgcd(a,c,x,y);
x=x*b%c;
while(x<0) x+=c;
printf("%lld\n",x);
return ;
}
void Solve3(ll a,ll b,ll c) {
Mp.clear();
if(!(a%c)) {
puts("Orz, I cannot find x!");
return ;
}
ll m=ceil(sqrt(c));
ll t=b;
for (int i=0;i<=m;i++) {
Mp[t]=i;
t=t*a%c;
}
ll s=Powe(a,m,c);t=s;
for (int i=1;i<=m;i++) {
ll v=Mp[t];
if (v!=0) {
printf("%lld\n",i*m-v);
return;
}
t=t*s%c;
}
puts("Orz, I cannot find x!");
}
int main() {
read(T);read(k);
while(T--) {
ll a,b,c;
read(a);read(b);read(c);
if(k==1) Solve1(a,b,c);
else if(k==2) Solve2(a,b,c);
else Solve3(a,b,c);
}
return 0;
}
/*
3 1
2 1 3
2 2 3
2 3 3
*/
/*
3 2
2 1 3
2 2 3
2 3 3
*/
转载于:https://www.cnblogs.com/Apocrypha/p/9435621.html
相关资源：JAVA上百实例源码以及开源项目
