众所周知,北上广深是中国非常一线的城市,北京是首都,地处……
正片开始!
一、BSGS基础算法
实现目标: A x ≡ B ( m o d P ) , ( gcd ( P , A ) = 1 ) A^x\equiv B(\mod P),(\gcd(P,A)=1) Ax≡B(modP),(gcd(P,A)=1)求最小的 x x x
很明显,如果暴力枚举,时间是 O ( P ) O(P) O(P)的,只要题目数据范围大,就死定了。愿意的人欢迎尝试(无100警告)
于是,考虑 ~ 莫队
~~~~~~~~~~~~~~~~ 分块
~~~~~~~~~~~~~~~~ BSGS
为什么我要提前两个?
因为BSGS本质就是分块!
简单讲解一下,就是将本来 P P P种情况,平均分成了$\sqrt p $份,对每份内进行预处理
不直观?好,那就用直观的式子吧!
令 x = k p − t \texttt{令}x=k\sqrt p-t 令x=kp−t
即 A k p ≡ A t B ( m o d p ) \texttt{即}A^{k\sqrt p}\equiv A^tB (\mod p) 即Akp≡AtB(modp)
于是,找个哈希表维护一下后面的即可
IO::pin>>y>>z>>p;
gp_hash_table<int,int> ht;
int f,s;
bool flg;
ht.clear();
f=ceil(sqrt(p));
s=1;
flg=1;
for(int i=1; i<=f; i++)s=1ll*s*y%p,ht[1ll*z*s%p]=i;
for(int j=1,k=s; j<=f; j++) {if(ht[k]&&flg) {wt(((1ll*j*f-ht[k])%p+p)%p,'\n');flg=0;}k=(1ll*s*k)%p;}if(flg)puts("Orz, I cannot find x!");
附赠模板代码
#pragma GCC optimize(1,"inline","Ofast")
#pragma GCC optimize(2,"inline","Ofast")
#pragma GCC optimize(3,"inline","Ofast")
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
namespace IO {class input {private:bool isdigit(char c) {return ('0'<=c&&c<='9');}public:input operator>>(int &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(short &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(bool &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(long &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(long long &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(__int128 &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(unsigned int &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(unsigned short &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(unsigned long &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(unsigned long long &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(unsigned __int128 &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(double &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=x*10+(c^48),c=getchar();if(!y)x=-x;if(!isdigit(c))if(c!='.')return *this;double z=1;while(isdigit(c))z/=10.,x=x+z*(c^48),getchar();return *this;}input operator>>(long double &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=x*10+(c^48),c=getchar();if(!y)x=-x;if(!isdigit(c))if(c!='.')return *this;double z=1;while(isdigit(c))z/=10.,x=x+z*(c^48),c=getchar();return *this;}input operator>>(float &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=x*10+(c^48),c=getchar();if(!y)x=-x;if(!isdigit(c))if(c!='.')return *this;double z=1;while(isdigit(c))z/=10.,x=x+z*(c^48),c=getchar();return *this;}input operator>>(std::string &x) {char c=getchar();x.clear();while(!(c!=' '&&c!='\n'&&c!=' '&&c!=EOF&&c))c=getchar();while(c!=' '&&c!='\n'&&c!=' '&&c!=EOF&&c) {x.push_back(c);c=getchar();}return *this;}input operator>>(char *x) {char c=getchar();int cnt=0;while(!(c!=' '&&c!='\n'&&c!=' '&&c!=EOF&&c))c=getchar();while(c!=' '&&c!='\n'&&c!=' '&&c!=EOF&&c) {x[cnt++]=c;c=getchar();}return *this;}input operator>>(char x) {x=getchar();return *this;}} pin;
};
inline void wt(char ch) {putchar(ch);
}
template<class T>
inline void wt(T x) {static char ch[40];int p=0;if(x<0)putchar('-'),x=-x;doch[++p]=(x%10)^48,x/=10;while(x);while(p)putchar(ch[p--]);
}
template<class T,class... U>
inline void wt(T x,U ...t) {wt(x),wt(t...);
}
#define int long long
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define frep(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define lqrep(i,a,v) for(int i=hd[a],v=e[i].v;i>=i##end;i=e[i].nxt,v=e[i].v)
const int N=1e5+7;
main() {
}
//目前快速输出pout还未搞定哦
到此就结束了吗?
当然不是!!!!!!!!!!
如果没有 gcd ( P , A ) = 1 \gcd(P,A)=1 gcd(P,A)=1的话,前面的一切都成了一纸空文
那该如何?
如果不需要的旅客们可以摆烂了,以下是扩展板
二、BSGS基础算法
不妨设 gcd ( P , A ) = d \gcd(P,A)=d gcd(P,A)=d
A x ≡ B ( m o d P ) − > ( A ′ × d ) x ≡ B ′ × d ( m o d P ) − > ( A ′ × d ) x − 1 ≡ B ′ ∗ A ′ − 1 ( m o d P ) A^x\equiv B(\mod P)->\\(A'\times d)^x\equiv B'\times d(\mod P)->\\(A'\times d)^{x-1}\equiv B'*A'^{-1}(\mod P) Ax≡B(modP)−>(A′×d)x≡B′×d(modP)−>(A′×d)x−1≡B′∗A′−1(modP)
接着按上文求解即可