思路：应用欧几里得算法求
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0) { x=1,y=0;return ; }
exgcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-y*(a/b);
}
int main()
{
ll a,b,x,y;
cin>>a>>b;
exgcd(a,b,x,y);
cout<<(x%b+b)%b;
return 0;
}
线性同余：
在数论中，线性同余方程是最基本的同余方程，“线性”表示方程的未知数次数是一次，即形如：
ax≡b (mod n)的方程。此方程有解当且仅当 b 能够被 a 与 n 的最大公约数整除（记作 gcd(a,n) | b）。
线性同余方程
传送门：线性同余方程
思路：线性同余方程a*x≡b（mod m）可以转化为a*x+m*y=b。
该同余方程有解当且仅当b%gcd(a,m)== 0 ？？？,
证明：假如有一组整数x1,y1满足a*x1+m*y1=gcd(a,m),
此时有b=k*gcd(a,m)，则必有k*（a*x1+m*y1）=k*gcd（a,m）
有解时用扩展欧几里得算法求出一组整数解x1,y1,满足a*x1+m*y1=gcd(a,m),至于答案就是
x = x1*(b/gcd(a,m))
而通解的话，待续。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0) { x=1,y=0;return a; }
int d= exgcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-y*(a/b);
return d;
}
int main()
{
ll a,b,x,y,m;
int t;
cin>>t;
while(t--)
{
cin>>a>>b>>m;
ll d=exgcd(a,m,x,y);
if(b%d==0)
{
cout<<(ll)x*(b/d)%m<<endl;
}else
printf("impossible\n");
}
return 0;
}
传送门：计算器（三个愿望一次满足）
高次同余方程：
问题：给定整数a,b,p,其中a,p互质，求一个非负整数x，使得 a^x≡b( mod p )
朴素思路：
形如a^x≡b( mod p )一类问题，保证p是质数以及a,p互质的前提下，
首先根据飞马小定理可以得到 a^（p-1）≡1（mod p）,可以那么设x属于区间[0,p-2],通过枚举不同的x下 a^x（mod p）的值与b（mod p）的值进行对比，那么一定可以确保答案在0~p-2之间。
证明：a^（p-1）≡1（mod p）==a^ 0 ≡1（mod p），此时a的次方模p的数值已经完成了一个循环，再往后的更高次方mod p的值也是在（0~p-2）次方mod p之间。
优化思路：
上面的做法的时间复杂度是O（p），当p的值过大的时，时间复杂度也会线性递增。
因此这里可以使用一个BSGS算法来优化时间复杂度使其降低到√p，
设问题中的x为 i*t-j，其中有
t = √p 向上取整
i的范围是[0,t]
j的范围是[0,t-1];
由这条 i * t - j 就可以枚举出x属于[0,p]的所有情况了，接下来这一步
因为a,p互质，所以可以在模p意义下对a进行乘，除法运算。
原方程变为a^（ i * t - j ）≡b( mod p )————(a^t) ^i ≡ b * a ^ j ( mod p)
将所有的 b * a ^ j （mod p）的值插入一个哈希表，对等号左边计算出所有的(a^t) ^i （mod p）的值查询哈希表是否存在对应的j值。该问题有可能无解。
代码：
其中如果a是p的倍数情况下无解，
void get3(ll a,ll b,ll p)
{
map<ll,ll>mp;
b%=p;
if(a==0||a%p==0)
{
if(b==0) cout<<0<<endl;
else puts("-1);
return ;
}
ll t=(ll)(sqrt(p)+1);
for(int j=0;j<m;j++) //存所有的b * a ^ j
{
ll m=b*qmi(a,j,p)%p;
mp[m]=j;
}
a=qmi(a,t,p);
for(int i=0;i<=t;i++) //找(a^t) ^i
{
ll val=qmi(a,i,p);
if(mp.count(val))
{
cout<<i*t-mp[val]<<endl;
return ;
}
}
puts("-1");
}