题意：开发一个能算三种算法的工具 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;
}
0 条评论