当前位置:网站首页>Chinese remainder theorem acwing 204 Strange way of expressing integers
Chinese remainder theorem acwing 204 Strange way of expressing integers
2022-07-05 06:24:00 【T_ Y_ F666】
Chinese remainder theorem AcWing 204. Strange way to express integers
Original link
AcWing 204. Strange way to express integers
Algorithm tags
Math knowledge Congruence equation Expand the Chinese Remainder Theorem
Ideas
The picture is extracted from the solution of the question
Code
#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;
}
Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support
边栏推荐
猜你喜欢
【LeetCode】Easy | 20. Valid parentheses
快速使用Amazon MemoryDB并构建你专属的Redis内存数据库
How to make water ripple effect? This wave of water ripple effect pulls full of retro feeling
[wustctf2020] plain_ WP
Doing SQL performance optimization is really eye-catching
AE tutorial - path growth animation
MySQL怎么运行的系列(八)14张图说明白MySQL事务原子性和undo日志原理
博弈论 AcWing 891. Nim游戏
Quickly use Amazon memorydb and build your own redis memory database
容斥原理 AcWing 890. 能被整除的数
随机推荐
Error ora-28547 or ora-03135 when Navicat connects to Oracle Database
中国剩余定理 AcWing 204. 表达整数的奇怪方式
【LeetCode】Day95-有效的数独&矩阵置零
Leetcode-6110: number of incremental paths in the grid graph
高斯消元 AcWing 884. 高斯消元解异或线性方程组
Install opencv -- CONDA to establish a virtual environment and add the kernel of this environment in jupyter
LeetCode-54
Network security skills competition in Secondary Vocational Schools -- a tutorial article on middleware penetration testing in Guangxi regional competition
2022-5-the fourth week daily
Alibaba's new member "Lingyang" officially appeared, led by Peng Xinyu, Alibaba's vice president, and assembled a number of core department technical teams
区间问题 AcWing 906. 区间分组
【LeetCode】Day94-重塑矩阵
11-gorm-v2-03-basic query
Regulations for network security events of vocational group in 2022 Guizhou Vocational College skill competition
MySQL advanced part 2: the use of indexes
Niu Mei's math problems
容斥原理 AcWing 890. 能被整除的数
Leetcode stack related
Presentation of attribute value of an item
International Open Source firmware Foundation (osff) organization