再颓下去我真成区了
2026-07-13 16:30:53
发布于：广东
30阅读
0回复
0点赞
由于中考数学没考满分，所以我认识到自己不会数学。
rt，挑战一天学两个板子。
EXCRT
比 CRT 简单。
考虑同余方程组 。
显然 的值为 的任意解，其中 也是未知数。
移一下项，。
显然符合 exgcd 的形式。
解出任意一个 ，则原方程组就等价于方程 。
逐一合并即可。
输入是反着的；实现时开 __int128；实时取模，否则你得开 int256。
namespace cjdst{
typedef __int128 lll;
void exgcd(lll a, lll b, lll &x, lll &y, lll d){
if(b == 0){
x = d / a, y = 0;
return;
}
exgcd(b, a % b, y, x, d);
y -= a / b * x;
}
void read(lll &x){
ll tmp;
std::cin >> tmp;
x = tmp;
}
void solve(){
int n;
std::cin >> n;
std::vector <lll> a(n + 5), b(n + 5);
for(int i = 1; i <= n; i++){
read(a[i]), read(b[i]);
}
for(int i = 2; i <= n; i++){
lll x, y, mod = a[i - 1] / std::__gcd(a[i - 1], a[i]) * a[i];// y -> -y
exgcd(a[i - 1], a[i], x, y, b[i] - b[i - 1]);
x = (x % mod + mod) % mod;
lll cur = a[i - 1] * x + b[i - 1];
cur = (cur % mod) + mod % mod;
a[i] = mod, b[i] = cur;
}
std::cout << ll(b[n]) << '\n';
}
}
时间复杂度：。
高斯消元
就普通解方程的方法，你平常咋解方程就咋写，嗯对。反正能做到 。
然后这个竟然可以求逆矩阵？！
求证：若矩阵 同时进行相同的矩阵初等变换后，若 ，则此时 。
证明：
假设 。则我们可以将两矩阵的关系表示为 。
由矩阵乘法定义得，在经过一次相同的矩阵初等变换后，依然满足 的关系，自行证明不难。
嗯。
namespace cjdst{
const ll mod = 1e9 + 7;
ll ksm(ll x, ll y){
ll ans = 1;
while(y){
if(y & 1) ans = x * ans % mod;
x = x * x % mod, y >>= 1;
}
return ans;
}
void solve(){
int n;
std::cin >> n;
std::vector <std::vector <ll>> a(n + 5, std::vector <ll>(n + 5)), b = a;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
std::cin >> a[i][j];
}
b[i][i] = 1;
}
for(int i = 1; i <= n; i++){
for(int j = i; j <= n; j++){
if(a[j][i]){
std::swap(a[i], a[j]);
std::swap(b[i], b[j]);
break;
}
}
if(a[i][i] == 0){
std::cout << "No Solution\n";
return;
}
ll inv = ksm(a[i][i], mod - 2);
for(int j = 1; j <= n; j++){
a[i][j] = a[i][j] * inv % mod;
b[i][j] = b[i][j] * inv % mod;
}
for(int j = 1; j <= n; j++){
if(j == i) continue;
if(a[j][i]){
ll cur = a[j][i];
for(int k = 1; k <= n; k++){
a[j][k] = (a[j][k] - a[i][k] * cur % mod + mod) % mod;
b[j][k] = (b[j][k] - b[i][k] * cur % mod + mod) % mod;
}
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
std::cout << b[i][j] << ' ';
}
std::cout << '\n';
}
}
}
时间复杂度：。
有帮助，赞一个