保研机试训练Day-20

数论

中国剩余定理

给定 2n 个整数 a1,a2,…,an 和 m1,m2,…,mn，求一个最小的非负整数 x，满足 ∀i∈[1,n], x ≡ **mi (mod** ai)。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;

ll exgcd(ll a, ll b, ll &x, ll &y){
    if(!b){
        x = 1,y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main(){
    int n;
    cin >> n;
  
    bool has_answer = true;
    ll a1,m1;
  
    cin >> a1 >> m1;
  
    for(int i=0;i<n-1;i++){
        ll a2,m2;
        cin >> a2 >> m2;
  
        ll k1,k2;
        ll d = exgcd(a1,a2,k1,k2);
        if((m2 - m1) % d){
            has_answer = false;
            break;
        }
  
        k1 *= (m2 - m1) / d;
        ll t = a2 / d;
        k1 = (k1 % t + t) % t;
  
        m1 = a1 * k1 + m1;
        a1 = abs(a1 / d * a2);
    }
    if(has_answer){
        cout << (m1 % a1 + a1) % a1 << endl;
    }
    else{
        puts("-1");
    }
    return 0;
}

高斯消元

输入一个包含 n 个方程 n 个未知数的线性方程组。方程组中的系数为实数。求解这个方程组。

#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

const int N=110;
const double eps=1e-6;

double a[N][N];
int n;

void out(){
    for(int i=0;i<n;i++){
        for(int j=0;j<=n;j++){
            printf("%10.2lf",a[i][j]);
        }
        puts(" ");
    }
    puts(" ");
}

int gauss(){
    int r, c; //行r列c
    for(r = 0, c = 0; c < n; c++){
        int t = r;
        for(int i = r; i < n; i++)
            if(fabs(a[i][c]) > fabs(a[t][c]))
                t = i;
          
            if(fabs(a[t][c]) < eps) continue;
      
            for(int j = c; j <= n; j++) swap(a[t][j], a[r][j]);
            for(int j = n; j >= c; j--) a[r][j] /= a[r][c];
            for(int i = r + 1; i < n; i++)
                if(fabs(a[i][c]) > eps)
                    for(int j = n; j >= c; j--)
                        a[i][j] -= a[r][j] * a[i][c];
  
        r++;
  
        // out();
    }
    if(r < n){
        for(int i = r; i < n; i++)
            if(fabs(a[i][n]) > eps)
                return 2; //无解
      
        return 1; //有无数个解
    }
  
    for(int i=n-1;i >= 0; i--)
        for(int j = i + 1; j < n; j++)
            a[i][n] -= a[i][j] * a[j][n];
  
    return 0; //有唯一解
}

int main(){
    cin >> n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n+1;j++)
            cin >> a[i][j];
  
    int t = gauss();
    if(t == 0){
        for(int i=0;i<n;i++) printf("%.2lf\n",a[i][n]);
    }
    else if(t == 1) puts("Infinite group solutions");
    else puts("No solution");
  
    return 0;
}

中国剩余定理 && 高斯消元

数论

中国剩余定理

高斯消元

CATALOG

FEATURED TAGS