洛谷P3868 猜数字

2023/6/27 C++ 算法竞赛 数论 洛谷

一眼上去这不中国剩余定理板题，但一直WA最后一个点，经过漫长的调试后，原来爆long long了

于是第一次开了__int128_t，__int128_t不能正常输入输出，只能快读快输

[TJOI2009] 猜数字

题目描述

现有两组数字，每组 个。

第一组中的数字分别用 表示，第二组中的数字分别用 表示。

其中第二组中的数字是两两互素的。求最小的 ，满足对于 ，有 。

输入格式

第一行一个整数 。

第二行 个整数，表示：。

第三行 个整数，表示：。

输出格式

输出一行一个整数，为所求的答案 。

样例 #1

样例输入 #1

3
1 2 3
2 3 5

样例输出 #1

23

提示

对于 的数据：

，，，。

每个测试点时限 秒。

注意：对于 C/C++ 语言，对 位整型数应声明为 long long。

若使用 scanf，printf 函数（以及 fscanf，fprintf 等），应采用 %lld 标识符。

解

第一次代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const int N=12;
int a[N],b[N];
int exgcd(int a,int b,int &x,int &y)
{
    if(b==0){x=1;y=0;return a;}
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int inv_inverse(int a,int m)
{
    int x,y;
    exgcd(a,m,x,y);
    return (x%m+m)%m;
}
signed main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int M=1;
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
        M*=b[i];
    }
    for(int i=1;i<=n;i++)
        a[i]=(a[i]%b[i]+b[i])%b[i];
    if(n==1)
    {
        cout<<a[1]%b[1]<<'\n';
        return 0;
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int Mi=M/b[i];
        ans=(ans+a[i]*Mi%M*inv_inverse(Mi,b[i]))%M;
    }
    cout<<ans<<'\n';
    return 0;
}

会WA最后一个点

开了__int128_t后：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int __int128_t
const int N=12;
int a[N],b[N];
inline void read(int& a)
{
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    a = s * w;
}
void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
int exgcd(int a,int b,int &x,int &y)
{
    if(b==0){x=1;y=0;return a;}
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int inv_inverse(int a,int m)
{
    int x,y;
    exgcd(a,m,x,y);
    return (x%m+m)%m;
}
signed main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;
    read(n);
    for(int i=1;i<=n;i++)
        read(a[i]);
        // cin>>a[i];
    int M=1;
    for(int i=1;i<=n;i++)
    {
        read(b[i]);
        // cin>>b[i];
        M*=b[i];
    }
    for(int i=1;i<=n;i++)
        a[i]=(a[i]%b[i]+b[i])%b[i];
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int Mi=M/b[i];
        ans=(ans+a[i]*Mi%M*inv_inverse(Mi,b[i]))%M;
    }
    write(ans);
    // cout<<ans<<'\n';
    return 0;
}
img_show