Author: lllyouo
Date: 20250705
tag: 同余方程
link: https://www.luogu.com.cn/problem/P2613

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

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

int main() {
    // bx = a mod 19260817
    string sa, sb; cin >> sa >> sb;
    long long a = 0, b = 0;    

    for (int i = 0; i < sa.size(); i++) {
        a = (a * 10 + sa[i] - '0') % 19260817;
    }
    for (int i = 0; i < sa.size(); i++) {
        b = (b * 10 + sb[i] - '0') % 19260817;
    }
    
    // bx + 19260817y = a
    long long x0, y0;
    long long g = exgcd(b, 19260817, x0, y0);

    if (a % g) cout << "Angry!" << endl;
    else {
        long long x = a / g * x0;
        cout << (x % (19260817 / g) + (19260817 / g)) % (19260817 / g) << endl;   
    }
    
    return 0;
}