求助
查看原帖
求助
841612
xian_love楼主2024/12/7 15:12

为何我的__int128加上快读快写怎么都运行不对呢

#include <bits/stdc++.h>
using namespace std;
typedef __int128 LL;
inline __int128 read(){
    __int128 x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void print(__int128 x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}

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;
    a1 = read(); 
    // print(a1);      //a1,m1其实也是最终的答案,每次都在这两个变量上更改
    m1 = read();
    // cout << endl;
    // print(m1);
    //进行n - 1次合并方程
    //将两个方程合并为x = (a1 * k1 + m1) + k * (a1 * a2) / d;即x = k * a + m (k为任何数)也就是和题目中的同余方程无异了
    for (int i = 0; i < n - 1; i ++ )
    {
        LL a2,m2;
        a2 = read();
        m2 = read();
        // print(a2),print(m2);
        // cout << endl;
        LL k1,k2;
        LL d = exgcd(a1,a2,k1,k2);      //先用扩展欧几里得算法得出看k1和k2的一组解
        if ((m2 - m1) % d)              //只有(m2-m1)是a1和a2的最小公约数的倍数才算有解,因为这样只需要翻转倍数即可
        {
            has_answer = false;         //无解直接退出
            break;
        }
        k1 *= (m2 - m1) / d;            //对k1翻转,k2不用管,只要最后的答案k1即可
        LL t = a2 / d;
        k1 = (k1 % t + t) % t;          //这两步的目的就是因为k1也可以等于k1 + k * a2 / d,那么为了防止在程序中溢出,我们就将k1
                                        //变至0~t1的范围内
        
        m1 = a1 * k1 + m1;              //新的方程中的m为此式
        a1 = (a1 > 0) ? a1 : -a1;          //得出一个正的最小公倍数,即为新式中的a
    }
    if (has_answer) print((m1 % a1 + a1) % a1); //求最小的正解x,最终的答案就是将m模至0-a的范围内
    else puts("-1");
    return 0;
}
2024/12/7 15:12
加载中...