洛谷P3868 猜数字

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

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

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

[TJOI2009] 猜数字

题目描述

现有两组数字，每组 k 个。

第一组中的数字分别用 a1, a2, ⋯, ak 表示，第二组中的数字分别用 b1, b2, ⋯, bk 表示。

其中第二组中的数字是两两互素的。求最小的 n ∈ ℕ，满足对于 ∀i ∈ [1,k]，有 bi|(n−ai)。

输入格式

第一行一个整数 k。

第二行 k 个整数，表示：a1, a2, ⋯, ak。

第三行 k 个整数，表示：b1, b2, ⋯, bk。

输出格式

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

样例 #1

样例输入 #1

1
2
3
3
1 2 3
2 3 5

样例输出 #1

1
23

提示

对于 100% 的数据：

1 ≤ k ≤ 10，|ai| ≤ 109，1 ≤ bi ≤ 6 × 103，。

每个测试点时限 1 秒。

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

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

解

第一次代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#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后： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#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