中国剩余定理：

一、标版：
题目描述
现有两组数字，每组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：
23
说明
所有数据中，第一组数字的绝对值不超过10⁹（可能为负数），第二组数字均为不超过6000的正整数，且第二组里所有数的乘积不超过10¹⁸

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#define ll long long
using namespace std;
const int maxn=20;
ll a[maxn],m[maxn];
ll M=1;
int k;
ll q_pow(ll a,ll b,ll p)
{
    ll ans=0;
    while(b)
    {
        if(b&1) ans=(ans+a)%p;
        a=(a+a)%p;
        b>>=1;

    }
    return ans%p;
}

ll mypow(ll a,ll b,ll p)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=q_pow(ans,a,p);
        a=q_pow(a,a,p);
        b>>=1;
    }
    return ans;
}

ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }

    ll d=exgcd(b,a%b,x,y);

    ll z=x;
    x=y;
    y=z-a/b*y;
    return d;
}

ll china(void)
{
    ll ans=0;
    ll x,y;
    for(int i=1;i<=k;i++) M*=m[i];

    for(int i=1;i<=k;i++)
    {
        ll mi=M/m[i];
        ll d=exgcd(mi,m[i],x,y);
        x=(x%m[i]+m[i])%m[i];
        ans=(ans+q_pow(q_pow(a[i],mi,M),x,M));
    }
    return (ans%M+M)%M;
}




int main(void)
{

    scanf("%d",&k);
    for(int i=1;i<=k;i++)
    {
        scanf("%lld",&a[i]);
    }

    for(int i=1;i<=k;i++)
    {
        scanf("%lld",&m[i]);
    }

    for(int i=1;i<=k;i++)
    {
        a[i]=(a[i]%m[i]+m[i])%m[i];
    }

    printf("%lld\n",china());
    return 0;
}

二、扩展：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#define ll long long
using namespace std;
const int maxn=100010;
ll a[maxn],m[maxn];
int k;
ll q_pow(ll a,ll b,ll p)
{
    ll ans=0;
    while(b)
    {
        if(b&1) ans=(ans+a)%p;
        a=(a+a)%p;
        b>>=1;

    }
    return ans%p;
}

ll mypow(ll a,ll b,ll p)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=q_pow(ans,a,p);
        a=q_pow(a,a,p);
        b>>=1;
    }
    return ans;
}

ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }

    ll d=exgcd(b,a%b,x,y);

    ll z=x;
    x=y;
    y=z-a/b*y;
    return d;
}

ll china(void)
{
    ll ans=a[1];
    ll x,y;
    ll M=m[1];
    for(int i=2;i<=k;i++)
    {

        ll c=(a[i]-ans%m[i]+m[i])%m[i];

        ll d=exgcd(M,m[i],x,y);
        if(c%d!=0) return -1;

        x=q_pow(x,c/d,m[i]/d);

        ans=(ans+x*M);
        M=M*(m[i]/d);
        ans=(ans%M+M)%M;
    }
    return (ans%M+M)%M;
}




int main(void)
{

    scanf("%d",&k);

    for(int i=1;i<=k;i++)
    {
        scanf("%lld%lld",&m[i],&a[i]);
    }

    printf("%lld\n",china());
    return 0;
}