文章目录
前言
一、中国剩余定理
二、AcWing 204. 表达整数的奇怪方式
本题解析
AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解数学知识：中国剩余定理，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、中国剩余定理
即孙子定理，具体定理即推导见：孙子定理，注意中国剩余定理必须要求两两互质，本博客例题中没有限制两两互质，故不能直接套用中国剩余定理的公式，需要在基础之上进行变形
二、AcWing 204. 表达整数的奇怪方式
本题链接：AcWing 204. 表达整数的奇怪方式
本博客提供本题截图：
本题解析
理论推导见OI爷的博客：墨染空 ,
AC代码
#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; LL x = 0, m1, a1; cin >> m1 >> a1; for (int i = 0; i < n - 1; i ++ ) { LL m2, a2; cin >> m2 >> a2; LL k1, k2; LL 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; LL m = abs(m1 / d * m2); a1 = k1 * m1 + a1; m1 = m; } if (x != -1) x = (x % m1 + m1) % m1; cout << x << endl; return 0; }
三、时间复杂度
关于中国剩余定理各步操作的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
