#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100;
LL exgcd(LL a, LL b, LL &x, LL &y)
{
if(!b)
{
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
LL CRT(LL a[], LL m[], int n)
{
LL M = 1;
for(int i = 0; i < n; i++) M *= m[i];
LL res = 0;
for(int i = 0; i < n; i++)
{
LL x, y;
LL M_i = M / m[i];
LL d = exgcd(M_i, m[i], x, y);
res = (res + a[i] * M_i * x) % M;
}
return (res + M) % M;
}
int main()
{
LL a[N], m[N];
int n;
cin >> n;
for(int i = 0; i < n; i++)
scanf("%lld%lld", &a[i], &m[i]);
cout << CRT(a, m, n) << endl;
return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y)
{
if(!b)
{
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
int main()
{
int n;
cin >> n;
bool has_answer = true;
//作为第一组数据,同时存储每次合并后的结果
LL a1, m1;
cin >> a1 >> m1;
for(int i = 0; i < n-1; i++)
{
LL a2, m2;
scanf("%lld%lld", &a2, &m2);
LL k1, k2;
LL d = exgcd(a1, a2, k1, k2);
if((m2 - m1) % d)
{
has_answer = false;
break;
}
//求出一个解
k1 *= (m2 - m1) / d;
//求出最小整数解
LL t = a2 / d;
k1 = (k1 % t + t) % t;
//更新合并后的a1、m1
m1 = a1 * k1 + m1;
a1 = abs(a1 / d * a2);
}
//最小整数解
if(has_answer) cout << (m1 % a1 + a1) % a1 << endl;
else puts("-1");
return 0;
}
#include <iostream>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y)
{
if(!b)
{
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
int main()
{
int n;
cin >> n;
int a[10];
cout << "请输入a~i:";
for(int i = 0; i < 9; i++)
scanf("%d", &a[i]);
bool has_answer = true;
//作为第一组数据,同时存储每次合并后的结果
LL a1 = 10, m1 = a[0];
for(int i = 0; i < n-1; i++)
{
LL a2 = 10 - i - 1, m2 = a[i + 1];
LL k1, k2;
LL d = exgcd(a1, a2, k1, k2);
if((m2 - m1) % d)
{
has_answer = false;
break;
}
//求出一个解
k1 *= (m2 - m1) / d;
//求出最小整数解
LL t = a2 / d;
k1 = (k1 % t + t) % t;
//更新合并后的a1、m1
m1 = a1 * k1 + m1;
a1 = abs(a1 / d * a2);
}
//最小整数解
if(has_answer) cout << (m1 % a1 + a1) % a1 << endl;
else puts("-1");
return 0;
}
666,我惊为天人
嘿嘿
这么厉害吗
没没,太拉了