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

让我们愉悦的学习 QVQ

2018 11 . 6 修改

因为快退役了(立个flag)就看看自己写过的题解,没想到自己以前还是太native 了QwQ

对算法的理解还没透彻 , (自己惯性思维 判0为无解,但不知道为啥还是 AC了qwq


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

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

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

关于BSGS算法 可以看看这个

BSGS算法讲解 : 和下面的结合起来更好理解 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



struct Maps//手写哈希表让你 跑得飞快 OvO
{
    struct line
    {
        int u,v,val;
    }edge[maxn];//建边思路,模拟链表

    int has[maxn] , tot;

    void clear(){
        mem(has,0);
        tot = 0;
    }
    void add(int u,int v,int val){//正常的加边
        edge[++tot].val = val;
        edge[tot].v = v;
        edge[tot].u = has[u]; 
        has[u] = tot;
    }

    void insert(int key , int val){//注意起点为 key % maxn , 终点为key
        add(key % maxn , key , val);
    }//要mod , 是因为 has[u]的大小

    int query(int key){//遍历所有 , key % maxn 相同的值 ,如果相同并且,终点也相同则为同一个值
        for(int i = has[key % maxn] ; i ; i = edge[i].u){
            if(edge[i].v == key) return edge[i].val;
        }//不然就for下一条边,每一次判断
        return -1;
    }
}maps;

int gcd(int a,int b){
    return !b ? a : gcd(b , a % b);
}
ll mul(ll a , ll b , ll mod){
    a %= mod , b %= mod;
    return (a * b - (ll)(((long double)a * b + 0.5) / mod) * mod + mod) % mod; 
}
int ExBSGS(int a,int b,int p){//扩展ExBSGS 用于解决 p 为任何数的情况
    a %= p , b %= p ;
    if(b == 1) return 0;
    //特判 , 如果 b == 1 那么a ^ 0 = 1
    int t = 1 , cnt = 0;

    while(1){   
        int g = gcd(a,p);
        if(g == 1) break;//如果 a, p 没有最大公约数,表示已经是质数了
        if(b % g != 0) return -1;//是b % gcd !!! b不整除gcd 则无解
        p /= g , b /= g , t = mul(t , a / g , p);
        ++cnt;// 表示已经
        if(b == t) return cnt;
    }   

    Maps maps;
    maps.clear();
    int block = sqrt(p)+0.5;
    int nows = t ;
    int base = 1;
    int tmp = 1;
    fors(i,0,block){//从 幂 0 开始
        maps.insert(mul(base , b , p) , i);
        tmp = base;
        base = mul(base , a , p);
    }

    base = tmp;

    fors(i,1,block){
        nows = mul(nows, base , p);//注意要使用 gcd中的保存的幂 作为底,每次 *a^m
        if(maps.query(nows) != -1){
            return i * block - maps.query(nows) + cnt;//记得加上gcd中的次数
        }
    }
    return -1;
}




/* 普通的bsgs
LL BSGS(LL a , LL b , LL p){
    int block = sqrt(p) + 0.5;//类似分块 不过要 ceil
    int base = 1;//初始base = 1,先模拟 存 b * a^j 
    map<LL , LL> maps;
    int tmp = 0;//保留上一个的值 ,计算a ^ block 
    fors(i,0,block){//从 幂 0  开始
        maps[mul(base , b , p)] = i+1;//保留 i+1 当求解的时候,要-1
        tmp = base;
        base = mul(base , a , p);//每次直接乘以a,免去快速幂
    }
    base = tmp;//保留上一个的值

    fors(i,1,block){//开始查询 从 幂 1 开始
        if(maps[base]){//他、如果存在这个值则直接返回 ,要记得i 乘以 block
            return i * block - (maps[base] - 1);
        }
        base = mul(base , tmp , p);//每次计算 (a^m) ^i
    }
    return -1;//无解则返回 -1;
}*/

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 == -1) puts("Orz, I cannot find x!");//-1判断无解
            else write(ans),putchar(10);
        }
    }
    return 0;
}
分类: 文章

B_Z_B_Y

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

发表评论

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

你是机器人吗? =。= *