src/number-theory/crt.hpp

• View this file on GitHub
• Last update: 2025-07-19 14:29:34+09:00
• Include: #include "src/number-theory/crt.hpp"

Depends on

• src/number-theory/euclid.hpp

Code

#pragma once
#include "src/number-theory/euclid.hpp" 

/**
 * Author: Simon Lindholm
 * Date: 2019-05-22
 * License: CC0
 * Description: Chinese Remainder Theorem.
 *
 * \texttt{crt(a, m, b, n)} computes $x$ such that $x\equiv a \pmod m$, $x\equiv b \pmod n$.
 * If $|a| < m$ and $|b| < n$, $x$ will obey $0 \le x < \text{lcm}(m, n)$.
 * Assumes $mn < 2^{62}$.
 * If x0 and y0 is one of the solutions of ax + by = g, then the general solution is
 * x = x0 + k * (b / g) and y = y0 - k * (a / g).
 * Time: $\log(n)$
 * Status: Works
 */

ll crt(ll a,ll m,ll b,ll n){
	if(n>m)swap(a,b),swap(m,n);
	ll x,y,g=euclid(m,n,x,y);
	if((a-b)%g!=0)return -1LL; // no solution
	x=(b-a)%n*x%n/g*m+a;
	return x<0?x+m*n/g:x;
}

#line 2 "src/number-theory/euclid.hpp"

/**
 * Author: Unknown
 * Date: 2002-09-15
 * Source: predates tinyKACTL
 * Description: Finds two integers $x$ and $y$,such that $ax+by=\gcd(a,b)$. If
 * you just need gcd, use the built in \texttt{\_\_gcd} instead.
 * If $a$ and $b$ are coprime, then $x$ is the inverse of $a \pmod{b}$.
 * $x = x_0 + k * (b / g)$
 * $y = y_0 - k * (a / g)$
 */

ll euclid(ll a,ll b,ll &x,ll &y){
	if(!b)return x=1,y=0,a;
	ll d=euclid(b,a%b,y,x);
	return y-=a/b*x,d;
}
#line 3 "src/number-theory/crt.hpp"

/**
 * Author: Simon Lindholm
 * Date: 2019-05-22
 * License: CC0
 * Description: Chinese Remainder Theorem.
 *
 * \texttt{crt(a, m, b, n)} computes $x$ such that $x\equiv a \pmod m$, $x\equiv b \pmod n$.
 * If $|a| < m$ and $|b| < n$, $x$ will obey $0 \le x < \text{lcm}(m, n)$.
 * Assumes $mn < 2^{62}$.
 * If x0 and y0 is one of the solutions of ax + by = g, then the general solution is
 * x = x0 + k * (b / g) and y = y0 - k * (a / g).
 * Time: $\log(n)$
 * Status: Works
 */

ll crt(ll a,ll m,ll b,ll n){
	if(n>m)swap(a,b),swap(m,n);
	ll x,y,g=euclid(m,n,x,y);
	if((a-b)%g!=0)return -1LL; // no solution
	x=(b-a)%n*x%n/g*m+a;
	return x<0?x+m*n/g:x;
}

Back to top page