笔试时间：2023年9月8日 秋招

第一题

题目

求关于x的同余方程ax1≡(mod b)的最小正整数解。

输入描述

输入只有一行，包含两个正整数 a,b，用一个空格隔开。

对于40%的数据，2<=b<=1,000;

对于60%的数据，2<=b<=50,000,000;

对于100%的数据，2<=a,b<=2,000,000,000。

输出描述

输出只有一行，包含一个正整数x，即最小正整数解。输入数据保证一定有解。

样例输入

3 10

样例输出

7

参考题解

经典同余方程求解。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <algorithm>

using namespace std;

using ll = long long;

void extendedEuclidean(int a, int b, ll& x, ll& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return;
    }

    extendedEuclidean(b, a % b, x, y);

    ll t = x;
    x = y;
    y = t - a / b * y;
}

int main() {
    ll a, b;
    cin >> a >> b;

    ll x, y;
    extendedEuclidean(a, b, x, y);

    ll result = (x + b) % b;
    cout << result;

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    public static void exgcd(int a, int b, long[] result) {
        if (b == 0) {
            result[0] = 1;
            result[1] = 0;
            return;
        }
        exgcd(b, a % b, result);
        long t = result[0];
        result[0] = result[1];
        result[1] = t - a / b * result[1];
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        long a = input.nextLong();
        long b = input.nextLong();
        long[] result = new long[2];
        exgcd((int) a, (int) b, result);
        System.out.println((result[0] + b) % b);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

def exgcd(a, b):
    if b == 0:
        return 1, 0
    x, y = exgcd(b, a % b)
    t = x
    x = y
    y = t - a // b * y
    return x, y


a, b = map(int, input().split())
x, y = exgcd(a, b)
print((x + b) % b)

第二题

题目

输入两个大数字符串(超过int64范围的数)，计算大数的乘法，并输出结果。输入格式：两个字符串，表示要相乘的两个数，长度均不超过1000。输出格式:一个字符串，表示两个数的乘积。注意事项:输入保证两个字符串均为非负整数；不允许使用任何高精度库函数或类库。

输入描述

输入两个非空纯数字字符串

输出描述

输出乘积结果

样例输入

15869523698

854789632596

样例输出

13565104331286935260008

参考题解

注意判断字符串前缀的0，大数相乘。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string add(const string& a, const string& b) {
    string sum = "";
    int carry = 0;
    int i = a.size() - 1;
    int j = b.size() - 1;
    while (i >= 0 || j >= 0 || carry) {
        int x = i >= 0 ? a[i--] - '0' : 0;
        int y = j >= 0 ? b[j--] - '0' : 0;
        int z = x + y + carry;
        sum += to_string(z % 10);
        carry = z / 10;
    }
    reverse(sum.begin(), sum.end());
    return sum;
}

string multiply(const string& a, int b) {
    string product = "";
    int carry = 0;
    int i = a.size() - 1;
    while (i >= 0 || carry) {
        int x = i >= 0 ? a[i--] - '0' : 0;
        int z = x * b + carry;
        product += to_string(z % 10);
        carry = z / 10;
    }
    reverse(product.begin(), product.end());
    return product;
}

string multiplyStrings(const string& a, const string& b) {
    if (a == "0" || b == "0") {
        return "0";
    }
    string result = "0";
    int j = b.size() - 1;
    for (; j >= 0; --j) {
        string temp = multiply(a, b[j] - '0');
        temp += string(b.size() - j - 1, '0');
        result = add(result, temp);
    }
    return result;
}

int main() {
    string a, b;
    cin >> a >> b;
    string ans = multiplyStrings(a, b);
    cout << ans