题解

103 条题解

  • 2
    @ 2016-12-20 22:15:05

    来来来 让我装一波。。。。剩余定理、、搬运链接http://blog.csdn.net/d_x_d/article/details/48466957 其实挺简单的。。注意乘积还有和用long long就好了
    ```c
    #include<stdio.h>

    int main()
    {
    int n,a,b;
    scanf("%d",&n);
    scanf("%d%d",&a,&b);
    long long ans = b, c = a;
    int i;
    for(i=2; i <= n; i++)
    {
    scanf("%d%d",&a,&b);
    while(ans % a != b)
    ans += c;
    c *= a;
    }
    printf("%lld\n",ans);
    return 0;
    }
    ```

  • 1
    @ 2017-03-23 13:33:12

    #1 Accepted 1ms 332.0KiB
    #2 Accepted 1ms 336.0KiB
    #3 Accepted 1ms 480.0KiB
    #4 Accepted 1ms 460.0KiB
    #5 Accepted 1ms 332.0KiB
    #6 Accepted 1ms 328.0KiB
    #7 Accepted 1ms 332.0KiB
    #8 Accepted 1ms 504.0KiB
    #9 Accepted 1ms 328.0KiB
    #10 Accepted 1ms 328.0KiB
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #define ll long long
    using namespace std;
    ll M = 1, p[105], a[105], ans;
    void exgcd(ll a, ll b, ll &x, ll &y){
    if(b == 0) x = 1, y = 0;
    else {
    exgcd(b,a%b,y,x);
    y -= (a/b) * x;
    }
    }
    ll inv(ll a, ll b){
    ll x, y;
    exgcd(a,b,x,y);
    return (x%b+b)%b;
    }
    int main(){
    ll i, j, n, m;
    scanf("%lld", &n);
    for(i = 1; i <= n; i++){
    scanf("%lld %lld", &p[i], &a[i]);
    M *= p[i];
    }
    for(i = 1; i <= n; i++) p[i] = M / p[i];
    for(i = 1; i <= n; i++){
    ans += inv(p[i], M/p[i]) * a[i] * p[i] % M;
    }
    ans %= M;
    printf("%lld",ans);
    return 0;
    }

  • 0
    @ 2020-04-30 17:14:24

    这是一道中国剩余定理(孙子定理)的裸模板题
    加一个犇犇的空间(多亏他的讲解):

    下面来简单解释下中国剩余定理(孙子定理):
    1.定义:若m _1
    1
    ​ ,m _2
    2
    ​ \cdots⋯ m n
    n
    ​ 是两两互质的正整数,M= \prod
    {i=1}^n{m_i}∏
    i=1
    n
    ​ m
    i
    ​ ,M _i
    i
    ​ =M/m _i
    i
    ​ ,t _i
    i
    ​ 是线性同余方程M _i
    i
    ​ t _i
    i
    ​ ≡1(mod m _i
    i
    ​ )的一个解。对于任意的n个整数a _1
    1
    ​ ,a _2
    2
    ​ \cdots⋯ a _n
    n
    ​ ,则同余方程组:
    \begin{cases}x≡a_1(mod)m_1\x≡a_2(mod)m_2\ \cdots \cdots\x≡a_n(mod)m_n\\end{cases}











    x≡a
    1
    ​ (mod)m
    1


    x≡a
    2
    ​ (mod)m
    2


    ⋯⋯
    x≡a
    n
    ​ (mod)m
    n




    有整数解,方程组的解为x=a _1
    1
    ​ M _1
    1
    ​ t _1
    1
    ​ +a _2
    2
    ​ M _2
    2
    ​ t _2
    2
    ​ + \cdots⋯ +a _n
    n
    ​ M _n
    n
    ​ t _n
    n
    ​ .并且在%M意义下有唯一解。
    2.证明:因为M _i
    i
    ​ =M/m _i
    i
    ​ 是除m _i
    i
    ​ 之外所有模数的倍数,所以 \forall∀ (任意)k \not≠= i,a _i
    i
    ​ M _i
    i
    ​ t _i
    i
    ​ ≡0(mod m _k
    k
    ​ ).又因为a _i
    i
    ​ M _i
    i
    ​ t _i
    i
    ​ ≡a _i
    i
    ​ (mod m i
    i
    ​ ),
    所以代入x=
    \sum
    {i=1}^{n}{a_iM_it_i}
    i=1

    n
    ​ a
    i
    ​ M
    i
    ​ t
    i


    4.结论:中国剩余定理给出了模数两两互质的线性同余方程组的一个特殊解。方程组的通解可以表示为x+kM(k∈Z)。有些题目要求我们求出最小的非负整数解,只需把x对M取模,并让x落在0~M-1的范围内即可。
    4注: \prod_{i=1}^n{m_i}∏
    i=1
    n
    ​ m
    i
    ​ 表示m _i
    i
    ​ 从1一直累乘到n.
    5提示:看不懂也没事,多理解理解 (相当于没说) ╰( ̄▽ ̄)╭
    6算法实现:

    int intchina(int r)
    {
    int Mi,x,y,d,ans=0;M=1;
    for(int i=1;i<=r;i++) M*=m[i];
    for(int i=1;i<=r;i++){
    M[i]=M/m[i];
    exgcd(Mi,m[i],d,x,y);
    ans=(ans+Mi*x*a[i])%M;
    }
    return (ans+M)%M;
    }
    思路点拨:中国剩余定理的模板题(没什么可以点拨的,就一裸的板子题)
    code
    #include<map>
    #include<queue>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define ll long long
    ll a[11],b[11],n,mod=1,ans=0;
    void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
    {
    if(b==0) d=a,x=1,y=0;
    else{
    exgcd(b,a%b,d,x,y);
    ll temp=x;x=y;y=temp-a/b*y;
    }
    }
    void intchina()
    {
    ll each,x,y,d;
    for(ll i=1;i<=n;i++){
    each=mod/a[i];
    exgcd(each,a[i],d,x,y);
    ans=((ans+each*x*b[i])%mod+mod)%mod;
    }
    printf("%lld\n",ans);
    }
    int main()
    {
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++){
    scanf("%lld%lld",&a[i],&b[i]);
    mod*=a[i];
    }
    intchina();
    return 0;
    }

  • 0
    @ 2017-09-14 21:57:13

    我真的看不懂那个超短的代码,弱啊。。。

    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    #define LL long long
    using namespace std;
    int N;
    LL A[15], B[15], M=1;
    /*
    int QUICKPOW (int a, int k, int m) {
        
        int ans=1;
        while(k>0) {
            if (k&1) ans=ans*a%m;
            a=a*a%m;
            k>>=1;
        }
        return ans%m;
        
    }
    */
    LL EXGCD (LL a, LL b, LL &x, LL &y) {
        
        if (!b) {
            x=1;
            y=0;
            return a;   
        }
        LL g=EXGCD(b, a%b, x, y);
        LL t=x;
        x=y;
        y=t-a/b*y;
        return g;
        
    }
    LL IE (LL a, LL m) {
        
        //return QUICKPOW(a, m-2, m);
        LL x, y;
        EXGCD(a, m ,x, y);
        return (x%m+m)%m;
        
    }
    int main () {
        
        cin >> N;
        LL ans=0;
        for(int i=1; i<=N; i++) {
            cin >> B[i] >> A[i];    
            M*=B[i];
        }
        for(int i=1; i<=N; i++) {
            LL x=M/B[i], e=IE(x, B[i]);
            ans=ans+x*e*A[i]%M;
        }
        cout << ans%M;
        return 0;
        
    }
    
  • 0
    @ 2017-07-16 23:43:03

    裸的中国剩余定理为什么AC率才24%。。。

  • 0
    @ 2017-05-08 12:31:16
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    int n;
    long long a,b;
    
    int main()
    {
        scanf("%d",&n);
        long long cur = 0;
        long long t = 1;
        while(n--)
        {
            long long c,d; 
            scanf("%lld%lld",&c,&d);
            while(cur % c != d % c) 
                cur += t;
            t *= c;
        }
        printf("%lld",cur);
        return 0;
    }
         
    
  • 0
    @ 2017-01-18 20:07:56

    ##其实说白了就是:**中国剩余定理**
    数学问题,希望好好思考。
    特别注意,本代码使用了输入输出优化。
    C++如下:

    #include<cstdio>
    #define R register
    #define ll long long
    int s()
    {
    R char ch=getchar();
    R int x=ch-'0';
    for(;(ch=getchar())>='0'&&ch<='9';)
    x=x*10+ch-'0';
    return x;
    }
    int w(R ll r)
    {
    if(r>9)
    w(r/10);
    putchar(r%10+'0');
    }
    int main()
    {
    R int n,a,b;
    n=s();a=s();b=s();
    long long int gcd=a,ans=b;
    for(R int i=2;i<=n;i++)
    {
    a=s();b=s();
    while(ans%a!=b)
    ans+=gcd;
    gcd*=a;
    }
    w(ans);
    return 0;
    }

    这个程序的运行结果就是:

    编译成功

    foo.cpp: In function 'int w(long long int)':
    foo.cpp:17:1: warning: no return statement in function returning non-void [-Wreturn-type]
    }
    ^
    测试数据 #0: Accepted, time = 0 ms, mem = 536 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 544 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 536 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 544 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    Accepted, time = 0 ms, mem = 544 KiB, score = 100
    希望对大家有所帮助,接下来再接再厉!

  • 0
    @ 2016-11-27 23:26:59

    孙子

  • 0
    @ 2016-11-08 21:26:00

    扩展欧几里得 合并同余式
    ```
    #include <iostream>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    typedef long long ll;

    void exgcd(ll a,ll b,ll &gcd,ll &x,ll &y)
    {
    if (!b) {
    gcd=a; x=1; y=0;
    } else {
    exgcd(b,a%b,gcd,y,x); y-=x*(a/b);
    }
    }

    int main()
    {
    ll n,a[20],b[20]; cin>>n;
    for (ll i=1;i<=n;i++)
    {
    cin>>b[i]>>a[i];
    }
    for (ll i=1;i<n;i++)
    {
    ll gcd,x,y;
    exgcd(b[i],-b[i+1],gcd,x,y);
    x*=(a[i+1]-a[i])/gcd;
    a[i+1]=a[i]+x*b[i];
    b[i+1]*=b[i];
    a[i+1]%=b[i+1];
    }
    if (a[n]<0) {
    a[n]=b[n]-abs(a[n])%b[n];
    } else {
    a[n]%=b[n];
    }
    cout<<a[n]<<endl;
    return 0;
    }
    ```

  • 0
    @ 2016-08-23 02:09:00

    CRT
    #include"stdio.h"
    #include"iostream"
    using namespace std;
    typedef long long ll;
    int n,m[50],a[50];
    void E_gcd(ll a,ll b,ll &d,ll &x,ll &y)
    {
    if(!b) {d=a;x=1;y=0;}
    else{E_gcd(b,a%b,d,y,x);y-=x*(a/b);}
    }
    ll CRT()
    {
    ll M=1;
    ll ans=0;
    int i;
    for(i=1;i<=n;i++) //M=m1*m2*m3*...*mn
    M=M*m[i];

    for(i=1;i<=n;i++) //Mi=M/mi x是Mi的逆元
    {
    ll d,x,y;
    ll Mi=M/m[i];
    E_gcd(Mi,m[i],d,x,y);
    ans=(ans+a[i]*Mi*x)%M;
    }
    if(ans<0) ans+=M;
    return ans;
    }
    int main()
    {
    while(cin>>n)
    {
    for(int i=1;i<=n;i++)
    cin>>m[i]>>a[i];
    cout<<CRT()<<endl;
    }
    return 0;
    }

  • 0
    @ 2015-11-10 21:31:23

    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>

    int main()
    {
    int n;
    long long a,b;
    scanf("%d",&n);
    long long cur = 0;
    long long yin = 1;
    while(n--){
    long long c,d; scanf("%lld%lld",&c,&d);
    while(cur % c != d % c) cur += yin;
    yin *= c;
    }
    printf("%lld",cur);
    return 0;
    }

    提交第一次wrong了两个点,因为如果有 3个猪圈,1个猪剩。至少1只猪就够了。

  • 0
    @ 2015-11-06 20:59:19

    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int MAXN = 12;

    int m[MAXN], a[MAXN], n;

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

    }
    exgcd(b, a%b, x, y);
    ll tep = x;
    x = y;
    y = tep - (a/b)*y;
    }
    ll CRT(){
    ll M = 1, ans = 0;
    for(int i=1; i<=n; i++) M*=m[i];
    for(int i=1; i<=n; i++){
    ll x, y;
    ll Mi = M/m[i];
    exgcd(Mi, m[i], x, y);
    ans = (ans + Mi * x * a[i]) % M;
    }
    if(ans < 0) ans += M;
    return ans;
    }

    int main()
    {
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    scanf("%d%d", &m[i], &a[i]);
    printf("%lld\n", CRT());
    return 0;
    }
    NOIP2015赛前留念
    祝RP++
    ——linhui

  • 0
    @ 2015-11-03 08:20:35

    #include <iostream>
    #include <cstdio>
    using namespace std;
    #define LL long long
    LL A[15],T[15],M[15],_M[15];
    long long m=1;
    LL k_gcd(LL a,LL b,LL &d,LL &x,LL &y)
    {
    if(b==0)
    {
    d=a;
    x=1;
    y=0;
    }
    else
    {
    k_gcd(b,a%b,d,y,x);
    y-=x*(a/b);
    }
    }
    LL inverse(LL a,LL b)
    {
    LL X=0,Y=0,D=0;
    k_gcd(a,b,D,X,Y);
    return ((X%b)+b)%b;
    }
    int main()
    {
    LL N;
    cin>>N;
    for(int i=1;i<=N;++i)
    {
    cin>>M[i]>>A[i];
    m*=M[i];
    }
    for(int i=1;i<=N;++i)
    _M[i]=m/M[i];
    for(int i=1;i<=N;++i)
    T[i]=inverse(_M[i],M[i]);
    long long ans=0;
    for(int i=1;i<=N;++i)
    {
    long long aa=T[i]*A[i]*_M[i];
    ans+=aa;
    }
    cout<<ans%m<<endl;
    return 0;
    }

  • 0
    @ 2015-10-25 15:37:55

    #include <iostream>
    #include <cstdio>
    #include <vector>

    using namespace std;

    int n;
    vector<long long int>a;
    vector<long long int>b;

    vector<long long int>f;
    long long int ans;

    long long int m=1;

    int exgcd(long long int a,long long int b,long long int &x,long long int &y)
    {
    if(b==0)
    {
    x=1;
    y=0;
    return a;
    }
    long long int r=exgcd(b,a%b,x,y);
    long long int m=x;
    x=y;
    y=m-(a/b)*y;
    return r;
    }

    int main()
    {
    int i,j;
    scanf("%d",&n);
    for(i=0;i<n;++i)
    {
    scanf("%d",&j);
    a.push_back(j);
    scanf("%d",&j);
    b.push_back(j);
    f.push_back(0);
    m*=a[i];
    }
    for(i=0;i<n;++i)
    {
    exgcd(m/a[i],a[i],f[i],ans);
    f[i]=(f[i]%a[i]+a[i])%a[i];//==f[i]=(f[i]+a[i])%a[i]
    }
    ans=0;
    for(i=0;i<n;++i)
    {
    ans+=b[i]*f[i]*(m/a[i]);
    }
    cout<<ans%m;//最小值
    return 0;
    }

  • 0
    @ 2015-10-24 15:52:39

    记录信息
    评测状态 Accepted
    题目 P1164 曹冲养猪
    递交时间 2015-10-24 15:25:12
    代码语言 Pascal
    评测机 VijosEx
    消耗时间 14 ms
    消耗内存 772 KiB
    评测时间 2015-10-24 15:25:13
    评测结果
    编译成功

    Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
    Copyright (c) 1993-2014 by Florian Klaempfl and others
    Target OS: Win32 for i386
    Compiling foo.pas
    Linking foo.exe
    13 lines compiled, 0.1 sec , 29328 bytes code, 1628 bytes data
    测试数据 #0: Accepted, time = 0 ms, mem = 772 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 772 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 772 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 772 KiB, score = 10
    测试数据 #4: Accepted, time = 2 ms, mem = 772 KiB, score = 10
    测试数据 #5: Accepted, time = 2 ms, mem = 772 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 768 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 772 KiB, score = 10
    测试数据 #8: Accepted, time = 7 ms, mem = 772 KiB, score = 10
    测试数据 #9: Accepted, time = 3 ms, mem = 772 KiB, score = 10
    Accepted, time = 14 ms, mem = 772 KiB, score = 100
    代码
    var
    a,b,c,d:qword;
    n,i:longint;
    begin
    readln(n);
    readln(a,b);
    for i:=2 to n do
    begin
    readln(c,d);
    while b mod c<>d do b:=a+b;
    a:=a*c;
    end;
    writeln(b);
    end.

  • 0
    @ 2015-10-24 14:56:04

    很裸的中国剩余定理
    记 同余方程为 ans% a[i]=b[i];
    M=a[1]*a[2]*...*a[n];M[i]=M/a[i];t[i]为M[i]关于a[i]的逆元 则答案为( (b[1]*a[1]*t[1]+....b[n]*a[n]*t[n] ) % M+ M)%M

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    typedef long long LL;
    LL a[20],b[20],n,t,M=1,ni[20],t2,ans;

    void exgcd(LL a,LL b,LL &d,LL &x,LL &y){//d是gcd a,b,x,y,满足ax+by=d
    if(!b) {d=a;x=1;y=0;}
    else {exgcd(b,a%b,d,y,x);y-=x*(a/b);}
    }

    int main(){
    //freopen("1164.in","r",stdin);freopen("1164.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i],&b[i]),M*=a[i];
    for(int i=1;i<=n;i++){
    exgcd(M/a[i],a[i],t,ni[i],t2);
    ni[i]=(ni[i]%a[i]+a[i])%a[i];
    (ans+=b[i]*ni[i]*(M/a[i]))%=M;
    }
    if(ans<0) ans+=M;
    printf("%lld",ans);
    return 0;
    }

  • 0
    @ 2015-10-20 16:45:51

    中国剩余定理,见黑书P230。

    void solve() {
        for (int i = 1; i <= n; i++) {
            long long Mi = M / m[i], x, y;
            exgcd(Mi, m[i], x, y);
            ans = (ans + Mi * x * a[i]) % M;
        }
    }
    
  • 0
    @ 2015-08-18 21:32:33

    中国剩余定理......

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    typedef long long LL;
    int n;
    LL gcl(LL x,LL y)
    {
    if(x % y == 0)
    return y;
    else
    return ass(y,x % y);
    }
    int main()
    {
    while(scanf("%d",&n) == 1)
    {
    LL num = 0;
    LL ans = 0;
    LL k = 0;
    LL a,b;
    for(int i = 1; i <= n; i++)
    {
    scanf("%I64d%I64d",&a,&b);
    if(i == 1)
    {
    num = b;
    ans = a;
    continue;
    }
    for(int j = 0;;j++)
    {
    k = num + ans * j;
    if(k % a == b)
    break;
    }
    num = k;
    if(ans < b)
    swap(ans,b);
    ans = (ans * a) / gcl(ans,a);
    }
    printf("%I64d\n",num);
    }
    }

  • 0
    @ 2015-08-01 10:56:09

    #include<iostream>

    using namespace std;

    int main()
    {
    int n, a, b;
    cin>>n;
    cin>>a>>b;
    long long int gcd = a, ans = b;
    for(int i=2; i<=n; i++){
    cin>>a>>b;
    while(ans % a != b)
    ans += gcd;

    gcd *= a;

    }

    cout<<ans;
    return 0;
    }
    水一发

信息

ID
1164
难度
6
分类
数论 | 解线性同余方程 点击显示
标签
递交数
4593
已通过
1140
通过率
25%
被复制
1
上传者