书店网站怎么做,顺德建设网站,wordpress 域名映射,什么是响应式设计众所周知#xff0c;北上广深是中国非常一线的城市#xff0c;北京是首都#xff0c;地处……
正片开始#xff01;
一、BSGS基础算法
实现目标#xff1a; 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)…众所周知北上广深是中国非常一线的城市北京是首都地处……
正片开始
一、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{令}xk\sqrt p-t 令xkp −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::pinyzp;
gp_hash_tableint,int ht;
int f,s;
bool flg;
ht.clear();
fceil(sqrt(p));
s1;
flg1;
for(int i1; if; i)s1ll*s*y%p,ht[1ll*z*s%p]i;
for(int j1,ks; jf; j) {if(ht[k]flg) {wt(((1ll*j*f-ht[k])%pp)%p,\n);flg0;}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)
#includebits/stdc.h
#includebits/extc.h
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
namespace IO {class input {private:bool isdigit(char c) {return (0cc9);}public:input operator(int x) {x0;bool y1;char cgetchar();while(!isdigit(c))y(c!-),cgetchar();while(isdigit(c))x(x1)(x3)(c^48),cgetchar();if(!y)x-x;return *this;}input operator(short x) {x0;bool y1;char cgetchar();while(!isdigit(c))y(c!-),cgetchar();while(isdigit(c))x(x1)(x3)(c^48),cgetchar();if(!y)x-x;return *this;}input operator(bool x) {x0;bool y1;char cgetchar();while(!isdigit(c))y(c!-),cgetchar();while(isdigit(c))x(x1)(x3)(c^48),cgetchar();if(!y)x-x;return *this;}input operator(long x) {x0;bool y1;char cgetchar();while(!isdigit(c))y(c!-),cgetchar();while(isdigit(c))x(x1)(x3)(c^48),cgetchar();if(!y)x-x;return *this;}input operator(long long x) {x0;bool y1;char cgetchar();while(!isdigit(c))y(c!-),cgetchar();while(isdigit(c))x(x1)(x3)(c^48),cgetchar();if(!y)x-x;return *this;}input operator(__int128 x) {x0;bool y1;char cgetchar();while(!isdigit(c))y(c!-),cgetchar();while(isdigit(c))x(x1)(x3)(c^48),cgetchar();if(!y)x-x;return *this;}input operator(unsigned int x) {x0;bool y1;char cgetchar();while(!isdigit(c))y(c!-),cgetchar();while(isdigit(c))x(x1)(x3)(c^48),cgetchar();if(!y)x-x;return *this;}input operator(unsigned short x) {x0;bool y1;char cgetchar();while(!isdigit(c))y(c!-),cgetchar();while(isdigit(c))x(x1)(x3)(c^48),cgetchar();if(!y)x-x;return *this;}input operator(unsigned long x) {x0;bool y1;char cgetchar();while(!isdigit(c))y(c!-),cgetchar();while(isdigit(c))x(x1)(x3)(c^48),cgetchar();if(!y)x-x;return *this;}input operator(unsigned long long x) {x0;bool y1;char cgetchar();while(!isdigit(c))y(c!-),cgetchar();while(isdigit(c))x(x1)(x3)(c^48),cgetchar();if(!y)x-x;return *this;}input operator(unsigned __int128 x) {x0;bool y1;char cgetchar();while(!isdigit(c))y(c!-),cgetchar();while(isdigit(c))x(x1)(x3)(c^48),cgetchar();if(!y)x-x;return *this;}input operator(double x) {x0;bool y1;char cgetchar();while(!isdigit(c))y(c!-),cgetchar();while(isdigit(c))xx*10(c^48),cgetchar();if(!y)x-x;if(!isdigit(c))if(c!.)return *this;double z1;while(isdigit(c))z/10.,xxz*(c^48),getchar();return *this;}input operator(long double x) {x0;bool y1;char cgetchar();while(!isdigit(c))y(c!-),cgetchar();while(isdigit(c))xx*10(c^48),cgetchar();if(!y)x-x;if(!isdigit(c))if(c!.)return *this;double z1;while(isdigit(c))z/10.,xxz*(c^48),cgetchar();return *this;}input operator(float x) {x0;bool y1;char cgetchar();while(!isdigit(c))y(c!-),cgetchar();while(isdigit(c))xx*10(c^48),cgetchar();if(!y)x-x;if(!isdigit(c))if(c!.)return *this;double z1;while(isdigit(c))z/10.,xxz*(c^48),cgetchar();return *this;}input operator(std::string x) {char cgetchar();x.clear();while(!(c! c!\nc! c!EOFc))cgetchar();while(c! c!\nc! c!EOFc) {x.push_back(c);cgetchar();}return *this;}input operator(char *x) {char cgetchar();int cnt0;while(!(c! c!\nc! c!EOFc))cgetchar();while(c! c!\nc! c!EOFc) {x[cnt]c;cgetchar();}return *this;}input operator(char x) {xgetchar();return *this;}} pin;
};
inline void wt(char ch) {putchar(ch);
}
templateclass T
inline void wt(T x) {static char ch[40];int p0;if(x0)putchar(-),x-x;doch[p](x%10)^48,x/10;while(x);while(p)putchar(ch[p--]);
}
templateclass 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 ia,i##endb;ii##end;i)
#define frep(i,a,b) for(int ia,i##endb;ii##end;i--)
#define lqrep(i,a,v) for(int ihd[a],ve[i].v;ii##end;ie[i].nxt,ve[i].v)
const int N1e57;
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) 接着按上文求解即可
