网站的基础知识,机械网站建设案例,摄影网页制作,wordpress用oss这是一个中国剩余定理的问题。中国剩余定理是数论中的一个定理#xff0c;它给出了一组同余方程的解的存在性和唯一性。在这个问题中#xff0c;我们需要找到一个数#xff0c;使得它对给定的每个质数取余的结果等于给定的余数。
以下是一个使用C实现的解决方案#xff1a…
这是一个中国剩余定理的问题。中国剩余定理是数论中的一个定理它给出了一组同余方程的解的存在性和唯一性。在这个问题中我们需要找到一个数使得它对给定的每个质数取余的结果等于给定的余数。
以下是一个使用C实现的解决方案
#include iostream
#include vector
using namespace std;typedef long long ll;ll mul(ll a, ll b, ll mod) {ll res 0;while (b) {if (b 1) res (res a) % mod;a (a a) % mod;b 1;}return res;
}ll qpow(ll a, ll b, ll mod) {ll res 1;while (b) {if (b 1) res mul(res, a, mod);a mul(a, a, mod);b 1;}return res;
}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 inv(ll a, ll mod) {ll x, y;exgcd(a, mod, x, y);return (x % mod mod) % mod;
}int main() {vectorll A(8), a(8);for (int i 0; i 8; i) cin A[i];for (int i 0; i 8; i) cin a[i];ll M 1;for (int i 0; i 8; i) M * A[i];ll res 0;for (int i 0; i 8; i) {ll Mi M / A[i];res (res mul(mul(a[i], Mi, M), inv(Mi, A[i]), M)) % M;}cout res endl;return 0;
}在这个代码中我们首先定义了一些辅助函数包括mul函数用于计算两个数的乘积对模取余的结果qpow函数用于计算一个数的幂对模取余的结果exgcd函数用于计算扩展欧几里得算法的结果inv函数用于计算一个数的模逆元。然后我们读入输入的质数和余数计算出模数M并初始化结果res为0。接着我们遍历每一个质数和余数计算出Mi并更新res。最后我们输出res即满足条件的最小的一个数。
