中国剩余定理 AcWing 204. 表达整数的奇怪方式

忘是亡心i 2023-09-28 13:38 100阅读 0赞

## 中国剩余定理 AcWing 204. 表达整数的奇怪方式 ##

### 原题链接 ###

[AcWing 204. 表达整数的奇怪方式][AcWing 204.]

### 算法标签 ###

数学知识 同余方程 扩展中国剩余定理

### 思路 ###

![在这里插入图片描述][e58173880daf4511a5ba762d5a246110.png]  
![在这里插入图片描述][e170ab51e619406e957555f35cc891ec.png]  
![在这里插入图片描述][c31fbc2c6c424ff0a353412e6b50f524.png]  
![在这里插入图片描述][8422bb68cbda4e72b36a67602eda1d32.png]  
[图片摘自该题解][Link 1]

### 代码 ###

#include<bits/stdc++.h>
    #define int long long
    #define abs fabs
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>=b;--i)
    using namespace std;
    const int N = 105;
    int a[N][N], eps = 1e-8;
    int n;
    inline int read(){
       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();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    int exgcd(int a, int b, int &x, int &y){
        if(!b){
            x=1, y=0;
            return a;
        }else{
            int d=exgcd(b, a%b, y, x);
            y-=a/b*x;
            return d; 
        }
    }
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        n=read();
        int x=0, m1=read(), a1=read();
        rep(i, 0, n-1){
            int m2=read(), a2=read();
            int k1, k2;
            int d=exgcd(m1, m2, k1, k2);
            if((a2-a1)%d){
                x=-1;
                break;
            }
            k1*=(a2-a1)/d;
            k1=(k1 % (m2/d) + m2/d) % (m2/d);
            x=k1*m1+a1;
            int m=abs(m1/d*m2);
            a1=k1*m1+a1;
            m1=m;
        }
        if(x!=-1){
            x = (a1 % m1 + m1) % m1;
        }
        printf("%lld",x);
        return 0;
    }

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 204.]: https://www.acwing.com/problem/content/206/
[e58173880daf4511a5ba762d5a246110.png]: https://img-blog.csdnimg.cn/e58173880daf4511a5ba762d5a246110.png
[e170ab51e619406e957555f35cc891ec.png]: https://img-blog.csdnimg.cn/e170ab51e619406e957555f35cc891ec.png
[c31fbc2c6c424ff0a353412e6b50f524.png]: https://img-blog.csdnimg.cn/c31fbc2c6c424ff0a353412e6b50f524.png
[8422bb68cbda4e72b36a67602eda1d32.png]: https://img-blog.csdnimg.cn/8422bb68cbda4e72b36a67602eda1d32.png
[Link 1]: https://www.acwing.com/solution/content/3539/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://img-blog.csdnimg.cn/9cb4cb80a18345158f8a69e2f196e5b9.png