数论——线性同余方程、扩欧求解线性同余方程、线性组合、原根求解

线性同余方程

线性同余方程是形如的方程，其中a 、b、m 为给定的整数，x 是未知整数。

扩欧求解线性同余方程

void mod_slover(int a, int b, int n) {int d, x, y, x0;d = extend_gcd(a, n, x, y);if (b % d != 0)cout << "no answer";elsex0 = x * (b / d) % n;for (int i = 0; i <= d - 1; i++)cout << x0 + i * (n / d) % n;
}

#include <iostream>// 扩展欧几里得算法
int extendedEuclidean(int a, int b, int& x, int& y) {if (b == 0) {x = 1;y = 0;return a;}int x1, y1;int gcd = extendedEuclidean(b, a % b, x1, y1);x = y1;y = x1 - (a / b) * y1;return gcd;
}// 求解线性同余方程
bool solveLinearCongruence(int a, int b, int m, int& x) {int x0, y0;int gcd = extendedEuclidean(a, m, x0, y0);if (b % gcd!= 0) {return false;  // 无解}int mod = m / gcd;x = (x0 * (b / gcd)) % mod;if (x < 0) {x += mod;  // 保证解为正数}return true;
}int main() {int a = 3, b = 2, m = 5;int x;if (solveLinearCongruence(a, b, m, x)) {std::cout << "Solution of " << a << "x ≡ " << b << " (mod " << m << ") is: x = " << x << std::endl;} else {std::cout << "No solution exists." << std::endl;}return 0;
}

extendedEuclidean 函数用于计算两个数的最大公约数，并同时得到一组满足的解 x0 和 y0 。
solveLinearCongruence 函数首先调用 extendedEuclidean 计算 a 和 m 的最大公约数 gcd 。如果 b 不能被 gcd 整除，则方程无解。
若有解，计算出一个特解 x ，并通过取模操作和调整使其落在合法范围内（大于等于 0 且小于 m / gcd ）。

欧拉定理解线性同余方程

#include <iostream>// 计算欧拉函数
int eulerPhi(int n) {int result = n;for (int i = 2; i * i <= n; i++) {if (n % i == 0) {result -= result / i;while (n % i == 0) {n /= i;}}}if (n > 1) {result -= result / n;}return result;
}// 快速幂取模
int quickPow(int a, int b, int mod) {int res = 1;while (b) {if (b & 1) {res = (long long)res * a % mod;}a = (long long)a * a % mod;b >>= 1;}return res;
}// 利用欧拉定理求解线性同余方程
bool solveLinearCongruenceEuler(int a, int b, int m, int& x) {if (std::__gcd(a, m)!= 1) {return false;  // a 和 m 不互质，无解}int phi = eulerPhi(m);int invA = quickPow(a, phi - 1, m);  // a 的逆元x = (long long)invA * b % m;return true;
}int main() {int a = 3, b = 2, m = 5;int x;if (solveLinearCongruenceEuler(a, b, m, x)) {std::cout << "Solution of " << a << "x ≡ " << b << " (mod " << m << ") is: x = " << x << std::endl;} else {std::cout << "No solution exists." << std::endl;}return 0;
}

eulerPhi 函数用于计算给定整数的欧拉函数值，通过遍历质因数并进行相应的计算得到结果。
quickPow 函数用于快速计算幂的模运算。
solveLinearCongruenceEuler 函数首先判断 a和m 是否互质，如果不互质则方程无解。然后计算的欧拉函数值，找到 a的逆元，最后计算出 x 的值。

线性组合

线性同余方程组（模互素）

#include <iostream>// 扩展欧几里得算法
int extendedEuclidean(int a, int b, int& x, int& y) {if (b == 0) {x = 1;y = 0;return a;}int x1, y1;int gcd = extendedEuclidean(b, a % b, x1, y1);x = y1;y = x1 - (a / b) * y1;return gcd;
}// 计算模逆元
int modInverse(int a, int m) {int x, y;int gcd = extendedEuclidean(a, m, x, y);if (gcd!= 1) {std::cout << "Inverse doesn't exist" << std::endl;return -1;} else {return (x % m + m) % m;}
}// 中国剩余定理求解
int chineseRemainderTheorem(int a[], int m[], int n) {int M = 1;for (int i = 0; i < n; i++) {M *= m[i];}int x = 0;for (int i = 0; i < n; i++) {int Mi = M / m[i];int invMi = modInverse(Mi, m[i]);x += a[i] * Mi * invMi;}return x % M;
}int main() {int a[] = {2, 3, 2};int m[] = {3, 5, 7};int n = sizeof(a) / sizeof(a[0]);int result = chineseRemainderTheorem(a, m, n);std::cout << "Solution of the system is: " << result << std::endl;return 0;
}

中国剩余定理

int CRT（const int a[],const int m[],int n){int M = 1, ret = 0;for (int i = 1; i <= n; ++i)M *= m[i];for (int i = 1; i <= n; ++i) {int Mi = M / m[i], ti = inv(Mi, m[i]);ret = (ret + a[i] * a[i] * Mi * ti) % M;}return ret;
}
int inverse(int a, int b) {int x, y;excend_gcd(a, b, x, y);return x;
}

第一类高次同余方程

第二类高次同余方程

原根的解法

【模板】原根

#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
using ll = long long;
const int N=1e6+7;
int pr[N],ph[N],fc[9],u[11],v[11],a[N];
bool f[N],b[N],p[N],q[N];
void init(int n){//线性筛，b数组记录是否有原根b[2]=b[4]=ph[1]=1;int i,j,k,t=0;for(i=2;i<=n;++i){if(!f[i])pr[++t]=i,ph[i]=i-1;for(j=1;k=i*pr[j],k<=n&&j<=t;++j){f[k]=1;if(!(i%pr[j])){ph[k]=ph[i]*pr[j];break;}ph[k]=ph[i]*ph[pr[j]];}}for(i=2;i<=t;++i){for(j=1;j*1ll*pr[i]<=n;b[j*=pr[i]]=1);for(j=2;j*1ll*pr[i]<=n;b[j*=pr[i]]=1);}
}
int qp(int a,int b,int p){int r=1;while(b){if(b&1)r=r*1ll*a%p;a=a*1ll*a%p,b>>=1;}return r;
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T,n=0,m,d,i,j,k,t,o,s;cin>>T;for(i=1;i<=T;++i)cin>>u[i]>>v[i],n=n>u[i]?n:u[i];init(n);for(o=1;o<=T;++o){n=u[o],d=v[o];if(!b[n]){cout<<0<<"\n"<<endl;//如果没有原根;continue;}for(i=1,j=m=ph[n],t=0;1ll*pr[i]*pr[i]<=j;++i){if(!(j%pr[i])){fc[++t]=s=pr[i];//求出phi(n)的质因子;do j/=s;while(!(j%s));for(k=s;k<=m;k+=s)p[k]=1;}}if(j>1){fc[++t]=j;for(k=j;k<=m;k+=j)p[k]=1;}for(j=1;;++j){while(qp(j,m,n)!=1)++j;for(i=1;i<=t&&qp(j,m/fc[i],n)!=1;++i);if(i>t)break;//t个质因数都不符合}//快速幂求出最小原根j;for(t=j,i=1,s=0;i<=m;++i,t=t*1ll*j%n)if(!p[i])q[t]=1,++s;else p[i]=0;//通过最小原根求出所有原根cout<<s<<endl;for(i=1,j=0;i<n;++i){if(q[i]){q[i]=0,++j;if(j==d)j=0,cout<<i<<" ";}}//排序后从小到大输出;cout<<endl;}return 0;
}

init 函数：
- 这是一个线性筛法的函数，用于计算小于等于 n 的质数 pr 和每个数的欧拉函数值 ph，同时通过 b 数组标记是否有原根。
- 首先对一些特殊情况（如 2 和 4）进行初始化。
- 然后通过两层循环，筛选出质数并计算对应的欧拉函数值。对于每个数 i 和其对应的质数 pr[j]，根据是否整除的情况计算 ph[k]。
- 接着通过另外的循环标记有原根的数。
qp 函数：这是一个快速幂函数，用于计算 a 的 b 次幂对 p 取模的结果。
main 函数：
- 首先进行输入输出的同步设置。
- 读入测试用例的数量 T 和每个用例中的 u[i] 和 v[i]，并确定最大的 n 值。
- 调用 init 函数进行预处理。
- 对于每个测试用例：如果 n 没有原根，直接输出 0 并继续下一个用例。计算 phi(n) 的质因子并存放在 fc 数组中，同时标记相关的数。通过循环找到最小原根 j 。基于最小原根计算所有原根，统计原根的数量 s 并输出。按照要求输出第 d 个原根。

字符串的最大公约数

力扣1071.字符串的最大公因子

class Solution {
public:string gcdOfStrings(string str1, string str2) {return str1+str2!=str2+str1?"":str1.substr(0,gcd(str1.size(),str2.size()));}
};

str1 + str2 != str2 + str1：这检查str1后跟str2是否与str2后跟str1不相等。如果它们相等，这意味着一个字符串可以被看作是另一个的旋转，可能意味着某种重复或模式。
gcd(str1.size(), str2.size())：这计算str1和str2长度的最大公约数（GCD）。GCD是能同时整除两者的最大数。
str1.substr(0, gcd(str1.size(), str2.size()))：如果第一个条件为真，它会返回str1从索引0开始，长度等于str1和str2大小的GCD的子串。这对于找出字符串中的重复模式或重复的基本单元很有用。