3283: 运算器-白红宇

3283: 运算器

阅读量：5896 次

发布时间：2019-06-19

本文共 2077 字，大约阅读时间需要 6 分钟。

3283: 运算器

Time Limit: 20 Sec Memory Limit: 256 MB

Submit: 340 Solved: 105

[][][]

Description

操作有3种：

Input

第一行一个正整数N，描述数据组数。

接下来的N行，每行4个正整数Sum，y，z，p。

Sum表述询问类型，如上题所述。对于第2种要求，若X不存在，则输出“Math Error”

Output

要求有N行输出，每行一个整数，为询问的答案。

Sample Input

1 2 10 1000

2 3 1 1000

2 2 3 4

3 2 7 9

Sample Output

Math Error

HINT

操作1个数小于501。保证Y,Z,P小于10^9

操作2个数小于51 保证Y,Z,P小于10^9 P不一定为质数

操作3个数小于51 保证Y，Z小于10^9，P小于10^9

P不一定为质数

P<=10^9

假设分解质因数后,P=p1^s1*p2^s2*……保证pi^ki<=10^5

Source

操作1：快速幂

操作2：扩展BSGS

操作3：扩展lucas

#include
      
       #include
       
        #include
        
         using namespace std;typedef long long ll;struct Thash{    static const ll N=1e6+5,MOD=233333;    ll tot,val[N],h[N],next[N],head[MOD+100];    void clear(){tot=0;memset(head,0,sizeof head);}    void insert(ll H,ll VAL){        for(ll i=head[H%MOD];i;i=next[i]) if(h[i]==H){val[i]=VAL;return ;}        h[++tot]=H;val[tot]=VAL;next[tot]=head[H%MOD];head[H%MOD]=tot;    }    ll get(ll H){        for(ll i=head[H%MOD];i;i=next[i]) if(h[i]==H) return val[i];        return -1;    }}M;inline ll read(){    ll x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}ll fpow(ll a,ll p,ll mod){    ll res=1;    for(;p;p>>=1,a=a*a%mod) if(p&1) res=res*a%mod;    return res;}ll gcd(ll a,ll b){    if(!b) return a;    return gcd(b,a%b);}void exgcd(ll a,ll b,ll &d,ll &x,ll &y){    if(!b){d=a;x=1;y=0;return ;}    exgcd(b,a%b,d,y,x);    y-=a/b*x;}ll inv(ll a,ll p){    ll d,x,y;    exgcd(a,p,d,x,y);    return d==1?(x%p+p)%p:-1;}ll BSGS(ll a,ll b,ll mod){    M.clear();    ll m=(ll)ceil(sqrt(mod+0.5));    ll t=1;    for(ll i=0;i
         
          1) ans=(ans+C(n,m,x,x,MOD))%MOD;    printf("%lld\n",ans);}int main(){    int T=read();    for(ll opt,y,z,p;T--;){        opt=read();y=read();z=read();p=read();        if(opt==1) printf("%lld\n",fpow(y,z,p));        if(opt==2) case2(y,z,p);        if(opt==3) case3(z,y,p);    }    return 0;}