Jump to content

Chinese remainder theorem: Difference between revisions

Chinese remainder theorem (view source)

Revision as of 11:27, 13 December 2020

70 bytes removed ,  3 years ago
→‎{{header|C++}}
(added Crystal implementation (translation of Ruby implementation))
Line 341:
 
=={{header|C++}}==
<lang cpp>#include// <iostream>Requires C++17
#include <iostream>
#include <numeric>
#include <vector>
#include <execution>
 
template<typename _Ty> _Ty mulInv(_Ty a, _Ty b) {
using namespace std;
int_Ty x0b0 = 0b;▼
 
int_Ty x1x0 = 10;▼
int mulInv(int a, int b) {
int_Ty b0x1 = b1;
▲ int x0 = 0;
▲ int x1 = 1;
 
if (b == 1) {
Line 358 ⟶ 357:
 
while (a > 1) {
int_Ty q = a / b;
int_Ty amb = a % b;
a = b;
b = amb;
 
int_Ty xqx = x1 - q * x0;
x1 = x0;
x0 = xqx;
Line 375 ⟶ 374:
}
 
inttemplate<typename _Ty> _Ty chineseRemainder(std::vector<int_Ty> n, std::vector<int_Ty> a) {
int_Ty prod = std::reduce(std::execution::seq, n.begin(), n.end(), (_Ty)1, [](int_Ty a, int_Ty b) { return a * b; });
 
int_Ty sm = 0;
for (int i = 0; i < n.size(); i++) {
int_Ty p = prod / n[i];
sm += a[i] * mulInv(p, n[i]) * p;
}
 
return sm % prod;
}
 
int main() {
vector<int> n = { 3, 5, 7 };
vector<int> a = { 2, 3, 2 };
 
cout << chineseRemainder(n,a) << endl;
 
return 0;
}</lang>
{{out}}
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/239383"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information