The method of doubling large numbers to find (expand) the Chinese Remainder Theorem

Oct 2, 2023#oi #zhx #qbxt7

AI Translation

This post is translated from Chinese into English through AI.View Original

AI-generated summary

The content discusses a brute-force method for merging numbers to determine how much needs to be added for compliance with certain conditions. Although the time complexity may seem confusing, the template problem runs efficiently. There is a noted risk of getting stuck, especially with smaller values of 'n', but typically only one point may cause an issue. A C++ code snippet is provided, illustrating the merging process.

Brute Force#

Brute force merges each number with another number, calculating how much needs to be added to meet the requirements.

The time complexity looks confusing, but in reality, template problems run quite fast.

However, there is a risk of getting stuck; according to zhx, the smaller n is, the easier it is to get stuck, but at most it will only get stuck at one point (

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;

void Merge(int &b1, int &a1, int b2, int a2)
{
	if(a1 < a2) swap(b1, b2), swap(a1, a2);
	while(b1 % a2 != b2)
	{
		b1 += a1;
	}
	a1 = a1 / __gcd(a1, a2) * a2;
}
//a is the modulus, b is the remainder 
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	int bstar = 0, astar = 1;
	int b, a;
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		cin >> a >> b;
		b%= a;
		Merge(bstar, astar, b, a);
	}

	printf("%lld", bstar);
	return 0;
}