解一类线性方程 [数学]

1.线性同余方程

https://www.luogu.org/problem/P1082

$a x + b y = c$ 有解需要 $g c d (a, b) ∣ c$
这题也算找逆元方法很多 https://blog.csdn.net/qq_40831340/article/details/100024550

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e6 + 10;
long long n, m;

long long exgcd(long long a, long long b, long long &x, long long &y) {
	if (b == 0) {
		x = 1, y = 0;
		return a;
	}
	int d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

signed main() {
	ios::sync_with_stdio(0);
	long long a, b;
	cin >> a >> b;
	long long x = 0, y = 0;
	exgcd(a, b, x, y);
	cout << (x % b + b) % b << endl;
	return 0;
}

青蛙约会

https://www.luogu.org/problem/P1516
exgcd 解是 ax0+by0 = gcd(a, b);
那样通解就是
x = c/d * x0 + k*b/d;
y = c/d * y0 - k * a/d;

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;

long long exgcd(long long a, long long b, long long &x, long long &y) {
	if (b == 0) {
		x = 1, y = 0;
		return a;
	}
	int d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

//*((x0(K/gcd(a,b)))%(l/gcd(a,b))+(l/gcd(a,b)))%(l/gcd(a,b))

signed main() {
	ll n, m, x, y, l;
	cin >> x >> y >> m >> n >> l;
	ll a = n - m;
	ll b = l;
	ll c = x - y;
	if(a < 0) a = -a, c = -c;
	ll x0 = 0, y0 = 0;
	ll gcd = exgcd(a, b, x0, y0);
	if(c%gcd != 0 ) cout << "Impossible" << endl;
	else cout << (x0*(c/gcd)%(l/gcd)+(l/gcd))%(l/gcd) << endl;
	return 0;
}

2.高次不定方程

$A^{x} \equiv B (m o d p)$
分为两种情况， p是质数和 p 不是质数的情况……

p 是质数的情况 p|A 且 B!=0
非素数当通过枚举等方法发现其在 $[0, p - 1]$ 内无整数解，则此方程无整数解（关于当 p 为质数时，方程一定在 $[0, p - 1]$ 有一个整数解

BSGS

~~北上广深算法。。。。。~~ 只算 p 是素数时可以

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
#define int long long

long long pow_mod(long long a, long long b, long long p) {
    long long res = 1;
    for(; b; b >>= 1) {
        if(b & 1)
            res = res * a % p;
        a = a * a % p;
    }
    return res;
}

unordered_map<int, int> V;

ll BSGS(ll A, ll B, ll C) {
    const int sizes = ceil(sqrt(C));
    ll base = B % C;
    V[base] = 0;
    for(int i = 1; i <= sizes; i++) {
        base = base * A % C;
        V[base] = i;
    }
    base = pow_mod(A, sizes, C);
    ll tmp = 1;
    for(ll i = 1; i <= sizes; i++) {
        tmp = tmp * base % C;
        if(V[tmp])
            return ((i * sizes - V[tmp]) % C + C) % C;
    }
    return -1;
}

signed main() {
    int p, b, n;
    cin >> p >> b >> n;
    int ans = BSGS(b, n, p);
    if(ans == -1)
        cout << "no solution" << endl;
    else
        cout << ans << endl;
    return 0;
}

中国剩余定理

EXCRT

#include<cstdio>
using namespace std;
typedef long long ll;
ll n;
ll a[100010],b[100010]; 
ll mul(ll A,ll B,ll mod) //快速乘取余 模板
{
    ll ans=0;
    while(B>0)
      {
        if(B & 1) ans=(ans+A%mod)%mod;
        A=(A+A)%mod;
        B>>=1;
      }
    return ans;
}
ll exgcd(ll A,ll B,ll &x,ll &y) //扩展欧几里得 模板
{
    if(!B)
      {
        x=1,y=0;
        return A;
      }
    ll d=exgcd(B,A%B,x,y);
    ll tmp=x;
    x=y , y=tmp-A/B*y;
    return d;
}
ll lcm(ll A,ll B) //求最小公倍数
{
    ll xxx,yyy;
    ll g=exgcd(A,B,xxx,yyy);
    return (A/g*B);
}
ll excrt() //重点:求解同余方程组
{
    ll x,y;
    ll M=b[1],ans=a[1]; //赋初值 
    //M为前k-1个数的最小公倍数，ans为前k-1个方程的通解
    for(int i=2;i<=n;i++)
      {
        ll A=M,B=b[i];
        ll C=(a[i]-ans%B+B)%B; //代表同余方程 ax≡c(mod b) 中a,b,c

        ll g=exgcd(A,B,x,y);
        //求得A,B的最大公约数，与同余方程ax≡gcd(a,b)(mod b)的解，

        if(C%g) return -1; //无解的情况

        x=mul(x,C/g,B); //求得x的值,x即t 
        ans+=x*M;  //获得前k个方程的通解
        M=lcm(M,B); //更改M的值
        ans=(ans%M+M)%M;
      }
    return ans;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
      scanf("%lld%lld",&b[i],&a[i]);
    ll ans=excrt();
    printf("%lld",ans);
}

ll exgcd(ll a,ll b,ll &x,ll &y) {
	if(!b) {
		x=1,y=0;
		return a;
	}
	ll d=exgcd(b,a%b,x,y);
	ll z=x;
	x=y;
	y=z-y*(a/b);
	return d;
}
int n;
ll excrt() {
	ll d,x,y;
	bool flag=true;
	for(int i=2; i<=n; i++) {
		ll c=m[i]-m[i-1];
		d=exgcd(a[i-1],a[i],x,y);
		if(c%d!=0) {
			flag=false;
			break;
		}
		ll t=a[i]/d;
		x=(x*(c/d)%t+t)%t;
		m[i]=a[i-1]*x+m[i-1];
		a[i]=a[i-1]*(a[i]/d);
	}
	if(!flag) return -1;
	return m[n];
}