题意:开发一个能算三种算法的工具QUQ

让我们愉悦的学习 QVQ

一道经典模板好题(真好做)很明显这是一道总结快速幂,扩展gcd,以及BSGS(知道的简单,不知道的有你好受)的题目。

不过这题最大的坑点就是处理负数解以及无解。详情见代码

关于BSGS算法 [XZYQvQ] dalao已经在站内写过了,OTz
再还有点麻烦的是EXGCD的非负数解:

$~~~~~a * x + b * y = d$

一遍$exgcd$后,等式两边$/gcd(a,b)$,在将$x * (d ~/ ~gcd(a,b)~)~mod~(b~/~gcd(a,b))$ ,然后就OK了qwq


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;
#define fors(i,a,b) for(int i=(a);i<=(b);++i)
typedef long long ll;
const int Size=1<<25;
inline char getch(){
    static char buf[Size],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,Size,stdin),p1==p2) ? EOF : *p1++;
}
#define int ll//精度需要
int read(){
    int s=0,f=1;
    char c=getch();
    while(c>'9' || c<'0'){if(c=='-') f=-1;c=getch();}
    while(c<='9' && c>='0'){s=(s<<1)+(s<<3)+c-'0';c=getch();}
    return s*f;
}
void write(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
#define max(x,y) ((x) > (y) ? (x) : (y))
#define min(x,y) ((x) < (y) ? (x) : (y))
// 以上皆为卡常数的简单操作


int n,tot,ans;

int pows(int a,int b,int p){
    int res=1;
    while(b){
        if(b&1) res=(res*a%p);
        a=(a*a%p);
        b>>=1;
    }
    return res;
}//快速幂

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int tmp=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return tmp;
}//递归求exgcd

/*
int mul(int a,int b,int mod){
    int res=0;
    while(b){
        if(b&1) res=(a+res)%mod;
        b>>=1;
        a=(a+a)%mod;
    }
    return res;
}*///防止溢出的乘,不过这里不需要


int BSGS(int a,int z,int p){
    map<ll,int> maps;//maps[]存值
    int tmps,block=sqrt(p)+0.5,tot=1;
    fors(i,0,block)
        maps[tot*z%p]=i+1,tmps=tot,tot=tot*a%p;
    tot=tmps;//先枚举一边的值再存起来,再枚举另一边的值
    for(int i=1;i<=block;++i,tot=tot*tmps%p)
        if(maps[tot]){//从小到大枚举,如果比对则为有解
            return (i*block-maps[tot]+1);//如果为0则无解
        }
    return 0;
}
signed  main()
{
    int t=read(),op=read();
    while(t--){
        int y=read(),z=read(),p=read();
        if(op==1){
            write(pows(y,z,p)),putchar(10);
        }
        else if(op==2){
            int a,b;
            int mgcd=exgcd(y,p,a,b),tmp=p/mgcd,tmpk=z/mgcd;
            if(z%mgcd) puts("Orz, I cannot find x!");//如果z不能整除mgcd则无解
            else {
                a=((a* tmpk % tmp)+tmp)%tmp;//等式/gcd(y,p) *a从负数到正数的操作
                write(a),putchar(10);
            } 
        }
        else if(op==3){
            int ans=BSGS(y,z,p);
            if(!ans) puts("Orz, I cannot find x!");
            else write(ans),putchar(10);
        }
    }
    return 0;
}
分类: 文章

B_Z_B_Y

虽然也包含些许残酷 , 时间毕竟对任何人都很温柔-。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *