1 Description

Given two arrays of \(n\) integers, \(num\) and \(rem\), find the minimum \(x\) that satisfies \(x\ mod\ num_i=rem_i (i=1,…,n)\).

2 Solution

Calculate the product of \(num\) as \(prod\).

Let \(nums_i\) divide prod as \(pp_i\).

And \(inv_i\) is the modular multiplicative inverse of \(pp_i\) with respect to \(num_i\) that can be solved by extended Euclid’s Algorithm.

Then \(x=\sum_1^n(rem_i*pp_i*inv_i)%prod\).

#include<bits/stdc++.h>
using namespace std;

int inv(int a, int m)
{
	int m0 = m, t, q;
	int x0 = 0, x1 = 1;
	if (m == 1)
		return 0;
	while (a > 1)
	{
		q = a / m;
		t = m;
		m = a % m;
		a = t;
		t = x0;
		x0 = x1 - q * x0;
		x1 = t;
	}
	if (x1 < 0)
		x1 = x1 + m0;
	return x1;
}

int CRT(vector<int> num, vector<int> rem)
{
	int prod = 1;
	for (int i = 0; i < num.size(); i++)
	{
		prod = prod * num[i];
	}
	int res = 0;
	int pp;
	for (int i = 0; i < num.size(); i++)
	{
		pp = prod / num[i];
		res = res + rem[i] * inv(pp, num[i])*pp;
	}
	return res % prod;
}

int main()
{
	int n;
	scanf("%d", &n);
	vector<int> num(n);
	vector<int> rem(n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &num[i]);
	}
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &rem[i]);
	}
	printf("%d\n",CRT(num,rem));
	system("pause");
	return 0;
}

Result:

3
3 4 5
2 3 1
11

Reference

[1] https://www.geeksforgeeks.org/chinese-remainder-theorem-set-2-implementation/

Leave a Reply

Your email address will not be published. Required fields are marked *