写一个计算器，能计算
数论杂题。 第一问快速幂，第二问exgcd，第三问BSGS.
#include <cstdio>#include <map>#include <iostream>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;int n,x,y,p,k,a,b;map<int,int> Mp;inline void reaD(int &x){ char Ch=getchar();x=0; for(;Ch>'9'||Ch<'0';Ch=getchar()); for(;Ch>='0'&&Ch<='9';x=x*10+Ch-'0',Ch=getchar());}inline ll solve_1(ll x,int y,int p){ ll k=1;x%=p; while(y){ if(y&1) k=1ll*k*x%p; x=1ll*x*x%p; y>>=1; } //PRintf("%lld/n",k); return k;}int gcd(int x,int y){return y?gcd(y,x%y):x;}void exgcd(int x,int y,int &a,int &b){ if(!y){a=1;b=0;return;} exgcd(y,x%y,a,b); int t=a;a=b;b=t-x/y*b;}inline void solve_2(int y,int z,int p){ int g=gcd(y,p); if(z%g) {puts("Orz, I cannot find x!");return;} y/=g;z/=g;p/=g; exgcd(y,p,a,b); a=(1ll*a*z%p+p)%p; printf("%lld/n",a);}inline void solve_3(int y,int z,int p){ y%=p; if(!y&&!z){puts("1");return;} if(!y){puts("Orz, I cannot find x!");return;} Mp.clear(); ll t=ceil(sqrt(1.0*p)),x=1,ine=1; Mp[1]=0; for(int i=1;i<t;i++){ x=1ll*x*y%p; if(Mp.count(x)) continue; Mp[x]=i; } ll k=solve_1(y,p-1-t,p); for(int i=0;i<t;i++){ if(Mp.count(1ll*z*ine%p)){printf("%lld/n",Mp[1ll*z*ine%p]+1ll*i*t);return ;} ine=1ll*ine*k%p; } puts("Orz, I cannot find x!");}int main(){ reaD(n);reaD(k); for(int i=1;i<=n;i++){ reaD(x);reaD(y);reaD(p); if(k==1) printf("%lld/n",solve_1(x,y,p)); else if(k==2) solve_2(x,y,p); else solve_3(x,y,p); }}新闻热点
疑难解答
