[Luogu3868] [TJOI2009]猜数字

发布时间：2020-12-14 04:21:02 所属栏目：大数据来源：网络整理

导读：题目描述现有两组数字，每组k个，第一组中的数字分别为：a1，a2，...，ak表示，第二组中的数字分别用b1，b2，...，bk表示。其中第二组中的数字是两两互素的。求最小的非负整数n，满足对于任意的i，n - ai能被bi整除。输入输出格式输入格式：输入数据的第

题目描述

现有两组数字，每组k个，第一组中的数字分别为：a1，a2，...，ak表示，第二组中的数字分别用b1，b2，...，bk表示。其中第二组中的数字是两两互素的。求最小的非负整数n，满足对于任意的i，n - ai能被bi整除。

输入输出格式

输入格式：

输入数据的第一行是一个整数k，（1 ≤ k ≤ 10）。接下来有两行，第一行是：a1，a2，...，ak，第二行是b1，b2，...，bk

输出格式：

输出所求的整数n。

输入输出样例

输入样例#1：?

3
1 2 3
2 3 5

输出样例#1：?

说明

所有数据中，第一组数字的绝对值不超过109（可能为负数），第二组数字均为不超过6000的正整数，且第二组里所有数的乘积不超过1018

每个测试点时限1秒

注意：对于C/C++语言，对64位整型数应声明为long long，如使用scanf,printf函数（以及fscanf,fprintf等），应采用%lld标识符。

裸的中国剩余定理，但是丧心病狂的出题人会让你爆longlong，所以只能用龟速乘。

记得龟速乘之前把逆元取模处理一下，要不然让你疯狂TLE。

#include <iostream> 
#include <cstdio>
using namespace std;
#define int long long
#define reg register
inline char gc() {
    static const int BS = 1 << 22;
    static unsigned char buf[BS],*st,*ed;
    if (st == ed) ed = buf + fread(st = buf,1,BS,stdin);
    return st == ed ? EOF : *st++;
}
#define gc getchar
inline int read() {
    int res = 0;char ch=gc();bool fu=0;
    while(!isdigit(ch))fu|=(ch==‘-‘),ch=gc();
    while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=gc();
    return fu?-res:res;
}
int lcm = 1,ans,M;
inline int mul(int x,int y) {
    int res = 0;
    while(y)
    {
        if (y & 1) res = (res + x) % lcm;
        x = (x + x) % lcm;
        y >>= 1;
    }
    return res;
}
void exgcd(int a,int b,int &x,int &y) {
    if (!b) {x = 1,y = 0;return ;}
    exgcd(b,a % b,x,y);
    int t = x;
    x = y,y = t - a / b * y;
}

int n;
int a[20],b[20];


signed main()
{
    n = read();
    for (reg int i = 1 ; i <= n ; i ++) a[i] = read();
    for (reg int i = 1 ; i <= n ; i ++) b[i] = read(),lcm *= b[i],a[i] = (a[i] % b[i] + b[i]) % b[i];
    for (reg int i = 1 ; i <= n ; i ++)
    {
        M = lcm / b[i];
        int niv,x;
        exgcd(M,b[i],niv,x);
        niv = (niv % b[i] + b[i]) % b[i];
        ans = (ans + mul(mul(a[i],niv),M)) % lcm;
    }
    ans = (ans % lcm + lcm) % lcm;
    cout << ans << endl;
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!