【luogu3868】【TJOI2009】猜数字[模板] [数论中国剩余定理]

P3868 [TJOI2009]猜数字

是一道中国剩余定理的模版题

m₁,m₂...m_n两两互质对于任意整数a₁,a₂...a_n有且只有一个解：

x=Σ^k_i=1 a_i*M/m_i*t_i (mod m1*m2..*mk) 其中M=m1*m2*...mk，t_i为同余方程M/m_i*t_i≡1(mod m_i)的解，即mi的逆元

所有数据中，第一组数字的绝对值不超过

关于快速乘来自题解大佬的说法

快速乘就是用来处理在爆long long 的边缘来回试探的乘法下要取模的一种骚操作

其实应该叫龟速乘

核心思想就是把一个数按二进制拆分，然后一位一位对应乘。

和快速幂差不多

int qmul(int a,int b,int mod)
{
    int ans=0;
    while(b)
    {
        if(b&1) ans=(ans+a)%mod;
        a=(a+a)%mod;b>>=1;
    }
    return ans;
}

中国剩余定理：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 ll k,a[15],m[15],M;
 5 
 6 template<class t>void rd(t &x)
 7 {
 8     x=0;int w=0;char ch=0;
 9     while(!isdigit(ch)) w|=ch=='-',ch=getchar();
10     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
11     x=w?-x:x;
12 }
13 
14 void exgcd(ll a,ll b,ll &x,ll &y)//扩展欧几里德
15 {
16     if(!b) {x=1,y=0;return;}
17     exgcd(b,a%b,x,y);
18     ll t=x;x=y,y=t-a/b*y;
19 }
20 
21 ll qmul(ll a,ll b,ll mod)
22 {
23     ll ans=0;
24     while(b)
25     {
26         if(b&1) ans=(ans+a)%mod;
27         a=(a+a)%mod;b>>=1;
28     }
29     return ans;
30 }
31 
32 ll china()
33 {
34     ll ans=0,M=1,x,y;
35     for(int i=1;i<=k;++i) M*=m[i];
36     for(int i=1;i<=k;++i)
37     {
38         ll Mi=M/m[i];
39         exgcd(Mi,m[i],x,y);//求同余方程解
40         x=(x%m[i]+m[i])%m[i];
41         ans=(ans+qmul(a[i],qmul(Mi,x,M),M))%M;//快速乘 防止爆long long 
42     }
43     return (ans+M)%M; 
44 }
45 
46 int main()
47 {
48     rd(k);
49     for(int i=1;i<=k;++i) rd(a[i]);
50     for(int i=1;i<=k;++i) rd(m[i]);
51     printf("%lld",china());
52     return 0;
53 }

【luogu3868】【TJOI2009】猜数字[模板] [数论 中国剩余定理]

【luogu3868】【TJOI2009】猜数字[模板] [数论中国剩余定理]