Introduction
For a better reading experience?
Prerequisite knowledge (obvious): \(\operatorname{lcm}(a,b)=\dfrac{ab}{\gcd(a,b)}\)
Linear Sieve for Primes
Click to view code``` bool visited[MAXN]; vector primes; long long result; void sieve(){ for(int i=2;i<=n;i++){ if(!visited[i]) primes.push_back(i); for(auto j:primes){ if(ij>n) break; visited[ij]=true; if(i%j==0) break; } } }
Example problem: B3716 Factorize Prime 3
Inequality Equation (exgcd)
============
Equations of the form \\(ax+by=c\\) (where \\(a,b\\) are integers) have solutions if and only if \\(\\gcd(a,b) \\mid c\\)
Euclidean algorithm: \\(\\gcd(a,b)=\\gcd(b,a \\bmod b)\\).
Solving \\(ax+by=\\gcd(a,b)\\):
When \\(a|b\\), \\(ax+by=\\gcd(a,b)\\) has solution \\(\\begin{cases}x=0\\\\y=1\\end{cases}\\)
\\(\\begin{aligned}\\because ax+by&=\\gcd(a,b)\\\\&=\\gcd(b,a \\bmod b)\\\\&=bx\_1+(a\\bmod b)y\_1\\\\&=bx\_1+(a-\\lfloor\\dfrac{a}{b}\\rfloor \\times b)y\_1\\\\&=bx\_1+(a-\\lfloor\\frac{a}{b}\\rfloor \\times b)y\_1\\\\&=ay\_1+b(x\_1-\\lfloor\\frac{a}{b}\\rfloor \\times y\_1) \\end{aligned}\\)
\\(\\therefore \\begin{cases}x=y\_1\\\\y=x\_1-\\lfloor \\frac{a}{b} \\rfloor \\times y\_1 \\end{cases}\\)
\\(\\therefore\\) Can be solved recursively.
Recursive function
----
Click to view code```
void gcd(int &x,int &y,int a,int b){
if(a%b==0){
x=0,y=1;
}else{
int xx,yy;
gcd(xx,yy,b,a%b);
x=yy;y=xx-a/b*yy;
}
}
Pérmann's Theorem
(This was added later on 2023.4.14) QWQ
Definition
For non-zero integers \(a,b\), there exist integers \(x,y\) such that \(ax+by=\gcd(a,b)\).
Then we see that the previous formula solves the equation from Pérmann's theorem.
Here's something I discovered myself: (though I haven't seen this mentioned in articles I've read, maybe because it's too simple)
To find solutions to \(ax+by=c\), where \(a,b\) are integers and \(\gcd(a,b)|c\).
First, solve \(ax+by=\gcd(a,b)\), let the solution be \(\begin{cases}x=x'\\y=y'\end{cases}\)
Let \(k=\dfrac{c}{\gcd(a,b)}\), then the solution to \(ax+by=c\) is \(\begin{cases}x=kx'\\y=ky'\end{cases}\)
That's all. QWQ
Further conclusions can be found in the links below.
Pérmann's Theorem
Modular Arithmetic
Concept
For two integers \(a\), \(b\), if they have the same remainder when divided by \(d\), they are said to be congruent modulo \(d\), denoted as:
[a \equiv b\pmod d ]A small fact
[a-k \times b=r \to a \equiv r \pmod b ] (\(k\) is any integer)
Euler's Totient Function
\(\varphi \leftarrow\) this functon.
Definition
Euler's totient function \(\varphi(n)\) counts the number of positive integers less than or equal to \(n\) that are relatively prime to \(n\) (\(\gcd(i,n)=1\) or \(n \perp i\)).
Note that \(\varphi(1)=1\).
By the way, \(1\) is relatively prime to any number.
Evidently, For a positive integer \(a\), \(a\) is prime if and only if \(\varphi(a)=a-1\).
Properties
Multiplicativity: If \(\gcd(a,b)=1\) (i.e., \(a \perp b\)), then \(\varphi(a \times b)=\varphi(a)\times\varphi(b)\).
Euler inversion: \(\sum\limits_{d \mid n}\varphi(d)=n\). (\(\sum_{d \mid n}F(d)\) means summing \(F(d)\) over all divisors \(d\) of \(n\))
Property three: For any prime \(p\), \(\varphi(p^k)=p^k-p^{k-1}\).
Proof of property three: There are \(p^k\) numbers less than or equal to \(p^k\). Among them, \(p,2\times p,3\times p...t\times p\) are not relatively prime to \(p\). Evidently, \(t=p^{k-1}\), so there are \(p^{k-1}\) numbers not relatively prime to \(p\), hence \(p^k-p^{k-1}\) numbers are relatively prime to \(p\), i.e., \(\varphi(p^k)=p^k-p^{k-1}\).
Computing Euler's Totient Function
Single value calculation: Let \(n\)'s unique factorization be \(n=p_1^{k_1} \times p_2^{k_2} \times ... \times p_s^{k_s}\) (evidently, \(p_1\) to \(p_s\) are all primes, and \(p_1^{k_1},p_2^{k_2}...p_s^{k_s}\) are pairwise coprime), then \(\varphi(n)=\prod\limits_{i=1}^s \varphi(p_i^{k_i})\), which can be computed using property three (essentially \(\varphi(n)=\prod\limits_{i=1}^s (p_i^{k_i}-p_i^{k_i-1})\)).
In code implementation, there is a simpler formula:
[\varphi(n)=n \times \prod\limits_{i=1}^s(1 - \frac{1}{p_i}) ]Code:
Click to view code``` int phi(int x){ int num=x; for(int i=2;ii<=x;i++){ if(x%i==0) num=num/i(i-1); while(x%i==0) x/=i; } if(x>1) num=num/x*(x-1); return num; }
Linear Sieve for Euler's Totient Function
-------
While linearly sieving primes, we can also sieve Euler's totient function. Let \\(p\\) be the smallest prime factor of \\(i\\), consider three cases:
1. \\(i\\) is prime, \\(\\varphi(i)=i-1\\).
2. \\(p\\) is a factor of \\(\\frac{i}{p}\\), \\(\\varphi(i)=\\varphi(\\frac{i}{p}) \\times p\\).
3. \\(p\\) and \\(\\frac{i}{p}\\) are coprime, \\(\\varphi(i)=\\varphi(\\frac{i}{p}) \\times \\varphi(p)\\).
Proof:
1. Evidently
2. Let \\(i=p^k \\times q\\), where \\(q\\) contains no factor \\(p\\). Then \\(\\varphi(i)=\\varphi(q) \\times \\varphi(p^k)=\\varphi(q) \\times (p^k-p^{k-1})=\\varphi(q) \\times p(p^{k-1}-p^{k-2})=\\varphi(q) \\times p \\times \\varphi(p\_{k-1})=\\varphi(\\frac{i}{p}) \\times p\\)
3. Follows from multiplicativity.
Example: P2158 \[SDOI2008\] Guard Formation.
Assume `C君` is at position \\((0,0)\\).
We notice that `C君` can see point \\((i,j)\\) if and only if \\(\\gcd(i,j)=1\\), and positions symmetric about the diagonal line from `C君`'s position are visible.
\[ans=2\sum\limits^{n-1}_ {i=1}\sum\limits^{i}_ {j=1} [\gcd(i,j)=1] +1 \]\[ans=2\sum\limits^{n-1}_ {i=1} \varphi(i) +1 \]Use linear sieve for Euler's totient function. Remember to handle \\(n=1\\) specially.
Code:
Click to view code```
#include<bits/stdc++.h>
#define XD 114514
#define MAXN 40010
using namespace std;
int n;
int phi[MAXN];
bool visited[MAXN];
vector<int> primes;
long long result;
void compute(){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!visited[i]) phi[i]=i-1,primes.push_back(i);
for(auto j:primes){
if(i*j>n) break;
visited[i*j]=true;
if(i%j==0){
phi[i*j]=phi[i]*j;break;
}
phi[i*j]=phi[i]*phi[j];
}
}
}
int main(){
cin>>n;
if(n==1){
cout<<"0";
return 0;
}
compute();
for(int i=1;i<n;i++) result+=phi[i];
cout<<result*2+1;
return 0;
}
October 9, 2023
Found a potentially useful identity:
[\sum\limits_{i=1}^ni[\gcd(n,i)=1]=\frac{\varphi(n)n}{2} ]Euler's Theorem
For any positive integers \(a,m\) with \(\gcd(a,m)=1\), it holds that: \(a^{\varphi(m)} \equiv 1 \pmod m\).
Inverse Elements
Supplement on Inverse Elements (by 2023.5.11)
Definition
For any positive integer \(x\) satisfying \(x \times x^{-1} \equiv 1 \pmod p\), \(x^{-1}\) is called the inverse of \(x\) modulo \(p\) (similar to ordinary inverse, but defined under modular arithmetic).
Properties (just remember these QWQ)
Existence theorem: An inverse of \(x\) modulo \(p\) exists if and only if \(\gcd(x,p)=1\).
Corollary: When \(p\) is prime, all integers in \([1, p − 1]\) have inverses modulo \(p\). Zero has no inverse.
Uniqueness theorem: If an inverse of \(x\) modulo \(p\) exists, it is unique.
Theorem: In modular arithmetic modulo a prime \(p\), all integers in \([1, p − 1]\) have distinct inverses.
Theorem: The inverse of an inverse equals the original element.
Computing Inverses
First, here's an example.
P1082 [NOIP2012] Congruence Equation
From the definition of inverse, this is a straightforward inverse problem (evidently).
Since the input guarantees a solution, the existance theorem implies \(\gcd(a,b)=1\).
Now compute the inverse.
[a \times x \equiv 1 \pmod b ][\therefore a\times x =1 + b \times k ][\therefore a\times x + b \times k = 1 ]
This is an indeterminate equation (since \(a,b\) are known, we just need to solve for \(x\)).
Given \(\gcd(a,b)=1\), we can use recursion to solve.
Finally, make sure \(x\) is reduced to the range \([1,b-1]\). QWQ
The code is as follows.
Click to view code``` #include<bits/stdc++.h> #define XD 114514 #define int long long using namespace std; inline void gcd(int &x,int &y,int a,int b){ if(a%b==0){ x=0,y=1; }else{ int xx,yy; gcd(xx,yy,b,a%b); x=yy; y=xx-a/b*yy; } } signed main(){ int a,b,x,y; cin>>a>>b; gcd(x,y,a,b); cout<<(x%b+b)%b; return 0; }
Alternatively, it can be written as below.
Click to view code```
#include<bits/stdc++.h>
#define XD 114514
#define int long long
using namespace std;
inline void gcd(int &x,int &y,int a,int b){
if(a%b==0){
x=0,y=1;
return;
}
gcd(y,x,b,a%b);
y-=a/b*x;
}
signed main(){
int a,b,x,y;
cin>>a>>b;
gcd(x,y,a,b);
cout<<(x%b+b)%b;
return 0;
}
Supplement
Written on 2023.5.25
Due to some complex concepts in Extended Chinese Remainder Theorem, it seems I had some misunderstanding before, so here is a supplement.
Consider a problem (this is self-made QWQ)
Solve \(ax \equiv b \pmod p\)
Following the above approach, we get \(ax+pk=b\)
By Pérmann's theorem, if \(\gcd(a,p) \nmid b\), there's no solution.
Let \(\gcd(a,p)=g\)
Use exgcd to find \(au+pv=g\)
\(\therefore a\dfrac{bu}{g}+p\dfrac{bv}{g}=g\dfrac{b}{g}=b\)
That is \(x=\dfrac{bu}{g}\), \(k=\dfrac{bv}{g}\)
This shows \(x_0\equiv \dfrac{bu}{g}\pmod p\) is a solution to \(ax\equiv b \pmod p\).
Let \(x_1\) be another solution.
Then \(ax_1 \equiv ax_0 \pmod p\)
So \(p \mid ax_1-ax_0\)
This implies \(\dfrac{p}{g} \mid \dfrac{a(x_1-x_0)}{g}\)
Since \(\dfrac{p}{g}\), \(\dfrac{a}{g}\) have no common factors.
Therefore \(\dfrac{p}{g} \mid x_1-x_0\)
That is \(x_1=x_0+k\dfrac{p}{g}\) (\(k \in \mathbb{Z}\))
Since solutions differing by multiples of \(p\) are considered equivalent, there are exactly \(g\) distinct solutions.
That is, take \(k=0,1,...,g-1\).
After learning Extended CRT, it becomes clear that \(ax+by=c\) doesn't necessarily have only one or no solution. (But in OI, we usually only need the minimal positive solution QWQ)
Seems obvious QWQ.
Euler's Theoremcontinued
Euler's theorem requires \(\gcd(a,m)=1\), implying \(a\) has an inverse modulo \(m\). Let's derive a formula QWQ.
[a^{\varphi(m)} \equiv 1 \pmod m ][a^{\varphi(m)}\times a^{-1} \equiv a^{-1} \pmod m ][a^{\varphi(m)-1} \equiv a^{-1} \pmod m ]Thus, we get another method to compute inverses (though not very practical).
When \(m\) is prime, \(a^{\varphi(m)} \equiv 1 \pmod m\) becomes \(a^{m-1} \equiv 1 \pmod m\) thus Fermat's little theorem emerges.
Fermat's Little Theorem
For any integer \(a\) and prime \(p\), \(a^{p-1} \equiv 1 \pmod p\).
From this formula, we can deduce:
[a^{-1} \equiv a^{p-2} \pmod{p} ]Thus, we get yet another method to compute inverses (compute \(a^{p-2} \bmod p\) using fast exponentiation).
Let's do an example QWQ P2613 [Template] Rational Modulo
Find \(\frac{a}{b} \bmod 19260817\).
Let's calculate.
[\frac{a}{b} \bmod 19260817 ][a \times b^{-1} \bmod 19260817 ]We only need to compute the inverse of \(b\) modulo \(19260817\). Since \(19260817\) is prime, use Fermat's little theorem.
No solution occurs when \(b\) is a multiple of \(19260817\), i.e., \(b \bmod 19260817 = 0\).
Direct code:
Click to view code``` #include<bits/stdc++.h> #define XD 114514 #define mod 19260817 using namespace std; inline long long read(){ char ch=getchar(),h;long long w=0; while(ch>'9' or ch<'0') h=ch,ch=getchar(); while(ch>='0' and ch<='9') w=(w10+(ch-'0'))%mod,ch=getchar(); if(h=='-') w=-w; return w; } long long a,b; inline long long power(long long x,long long k){ //Compute x^(mod-2)%mod long long ans=1; while(k){ if(k&1){ ans=x;ans%=mod; } x*=x;x%=mod; k>>=1; } return ans; } int main(){ a=read(),b=read(); if(b==0) cout<<"Angry!\n"; else cout<<a*power(b,mod-2)%mod; return 0; }
Linear Inverse Computation
-----
Let \\(inv\_i\\) denote the inverse of \\(i\\), with recurrence relation:
\[inv_i \equiv - \lfloor \frac{p}{i} \rfloor \times inv_{p \bmod i} \pmod p \]Base case is \\(inv\_1 = 1\\).
Time to derive again.
\[p=i \times k +r (r \in [1,n)) \]\[0 \equiv i \times k + r \pmod p \]\[r \equiv -i \times k \pmod p \]\[r \times r^{-1} \times i^{-1} \equiv -i \times i^{-1} \times r^{-1} \times k \pmod p \]\[i^{-1} \equiv -k \times r^{-1} \pmod p \]\[inv_i \equiv -\lfloor \frac{p}{i} \rfloor \times r^{-1} \pmod p \]\[inv_i \equiv -\lfloor \frac{p}{i} \rfloor \times inv_{p \bmod i} \pmod p \]Explanation: We set \\(p=i \\times k +r\\), where \\(r \\in \[1,n)\\), evidently, \\(k=\\lfloor \\frac{p}{i} \\rfloor\\), \\(r=p \\bmod i\\). This should clarify QWQ.
P3811 [Template] Multiplicative Inverse
Below is the code.
Click to view code```
#include<bits/stdc++.h>
#define XD 114514
#define MAXN 3000010
using namespace std;
int n,p,inv[MAXN];
int main(){
ios::sync_with_stdio(false);
cin>>n>>p;
inv[1]=1;
for(int i=2;i<=n;i++){
// inv[i]=(1ll*-(p/i)*inv[p%i]%p+p)%p;
inv[i]=1ll*(p-p/i)*inv[p%i]%p;//These two expressions are equivalent, but the latter saves one modulo operation
//Tested, first takes 398ms, second 338ms
}
for(int i=1;i<=n;i++) cout<<inv[i]<<'\n';
return 0;
}
A side note, I initially got TLE on two test cases for this problem, until I changed endl to '\n', which made it AC. This story tells us: cherish life, avoid endl.
B3717 Combination Problem
First know:
[C^m_n=\frac{n!}{m!(n-m)!} ]Evidently:
[C^m_n \equiv \frac{n!}{m!(n-m)!} \pmod {998244353} ]Then treat \(998244353\) as \(p\) otherwise typing a nine-digit number is tedious.
[\frac{n!}{m!(n-m)!} \bmod p= n! \times (m!)^{-1} \times [(n-m)!]^{-1} \bmod p ]Then compute \((m!)^{-1}\), evident:
[(m!)^{-1} \equiv 1^{-1} \times 2^{-1} \times 3^{-1} \times ... \times (m-1)^{-1} \times m^{-1} \pmod p]So compute inverses linearly first, then precompute all factorial inverses.
Code:
Click to view code``` #include<bits/stdc++.h> #define XD 114514
using namespace std; int T,N; const int p=998244353; int result; int main(){ ios::sync_with_stdio(false); cin>>T>>N; vector inv(N+1),a(N+1),b(N+1); inv[1]=1;//inv_i denotes the inverse of i a[1]=1;//a_i denotes i!'s value b[0]=b[1]=1;//b_i denotes the inverse of i!'s value for(int i=2;i<=N;i++){ inv[i]=1ll*(p-p/i)inv[p%i]%p; a[i]=1lla[i-1]i%p; b[i]=1llb[i-1]inv[i]%p; } while(T--){ int n,m,num=1; cin>>n>>m; num=1lla[n]b[m]%pb[n-m]%p; result^=num; } cout<<result; return 0; }
Wilson's Theorem
=====
(On 2023.7.11)
Theorem
--
If \\(p\\) is prime, then:
\[(p-1)! \equiv -1 \pmod p \]Proof
--
When \\(p=2\\), \\((p-1)! \\equiv 1 \\equiv -1 \\pmod p\\)
Take a prime \\(p > 2\\). For any positive integer \\(x\\)
(\\(1 \\le x \\le p-1\\)), it has an inverse, and these \\(p-1\\) numbers have distinct inverses. The numbers whose inverse is themselves are \\(1\\) and \\(p-1\\). We can group the remaining integers \\(2,3,4,...,p-1\\) into \\((p-3)/2\\) pairs, each pair's product is congruent to \\(1\\) modulo \\(p\\), which implies:
\[2\times3\times4\times...\times (p-2) \equiv 1 \pmod p \]Multiply both sides by \\(1\\) and \\(p-1\\):
\\((p-1)! \\equiv p-1 \\equiv -1 \\pmod p\\)
Q.E.D.
Its converse is:
> A positive integer \\(p\\) is prime if and only if:
>
> \[(p-1)! \equiv -1 \pmod p \]
Wilson's theorem is rarely used, but it might be needed in extended Lucas theorem.
Chinese Remainder Theorem (CRT)
===========
It solves a problem.
Problem
--
Given \\(n\\) linear congruences:
\[\begin{cases} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ ... \\ x \equiv a_n \pmod {m_n} \end{cases} \]Where \\(m\_1,m\_2,...,m\_n\\) are **pairwise coprime**. Find the general solution for \\(x\\).
Theorem
--
The system has a solution, and it's constructed as follows:
> Let \\(M=\\prod\\limits^n\_{i=1}m\_i\\) , \\(M\_i=\\frac{M}{m\_i}\\), \\(t\_i\\) be the inverse of \\(M\_i\\) modulo \\(m\_i\\).
> Then the unique general solution is:
>
> \[x \equiv \sum\limits^n_{i=1}a_i t_i M_i \pmod M \]
Proof
--
Evidently:
\[\gcd(M_i,m_i)=1 \]and,
\[M_it_i \equiv 1 \pmod {m_i} \](ensuring \\(M\_i\\) has an inverse modulo \\(m\_i\\))
\[\therefore a_iM_it_i \equiv a_i \pmod{m_i} \]Additionally, for a \\(j\\) (\\(j \\ne i\\)), since \\(m\_i | M\_j\\), we have \\(M\_j \\equiv 0 \\pmod{m\_i}\\).
\[\therefore a_iM_it_i+m_jM_jt_j \equiv a_i \pmod{m_i} \]\[\therefore a_iM_it_i + \sum\limits^n_{j=1,i\ne j} a_jM_jt_j \equiv a_i \pmod{m_i} \]\[\sum\limits^n_{i=1} a_iM_it_i \equiv a_i \pmod{m_i} \]This confirms that \\(x=\\sum\\limits^n\_{i=1} a\_iM\_it\_i\\) is a particular solution.
Using elementary math (simplified proof), we know that the difference between two particular solutions is a multiple of \\(M\\), thus \\(x+kM\\) is also a solution, proving uniqueness of the general solution.
Example
--
P1495 [Template] Chinese Remainder Theorem (CRT) / Cao Chong Herds
Template problem, direct code.
Click to view code```
#include<bits/stdc++.h>
#define XD 114514
#define MAXN 20
#define int long long
using namespace std;
int n;
void gcd(int &x,int &y,int a,int b){//Compute inverse
if(a%b==0){
x=0,y=1;
return;
}
gcd(y,x,b,a%b);
y-=a/b*x;
}
int a[MAXN],b[MAXN],M[MAXN],m=1,t[MAXN],result;
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];//x=ai*k+bi -> x mod ai=bi mod ai
m*=a[i];
}
for(int i=1;i<=n;i++){
M[i]=m/a[i];
int x=0,y=0;
gcd(x,y,M[i],a[i]);
t[i]=(x%a[i]+a[i])%a[i];
}
for(int i=1;i<=n;i++){
result+=b[i]*t[i]%m*M[i]%m;
result%=m;
}
cout<<result;
return 0;
}
P3868 [TJOI2009] Guess Number
[b | (n-a_i) ][n-a_i \equiv 0 \pmod{b_i} ][n \equiv a_i \pmod{b_i} ]Then apply template.
Extended Chinese Remainder Theorem
To be written after I learn it. QWQ
Finally studied it. QWQ (on 2023.5.23)
Find
[\begin{cases} x \equiv a_1 \pmod {b_1} \ x \equiv a_2 \pmod {b_2} \ ... \ x \equiv a_n \pmod {b_n} \end{cases} ]General solution for \(x\), but not guaranteed that \(b_1,b_2,...,b_n\) are pairwise coprime.
Start with the first two equations.
[\begin{cases} x \equiv a_1 \pmod {b_1} \ x \equiv a_2 \pmod {b_2} \end{cases} ]Can be rewritten as
[\begin{cases} x = b_1k_1+a_1 \ x = b_2k_2+a_2 \end{cases} ](\(k_1,k_2\) are arbitrary integers)
So
[b_1k_1+a_1=b_2k_2+a_2 ]Can be rewritten as
[b_1k_1+b_2k_2=a_2-a_1 ](\(k_2\) is not \(-k_2\) - explanation same as in exgcd for inverse computation)
Let \(g=\gcd(b_1,b_2)\)
Use exgcd to solve \(b_1h_1+b_2h_2=g\).
\(h_1,h_2\) are the \(x,y\) in \(ax+by=\gcd(a,b)\). This shouldn't be hard to understand QWQ
If the problem does not guarantee a solution, check if \((a_2-a_1)\) is divisible by \(g\). If \(g \nmid (a_2-a_1)\), then no solution.
After finding \(h_1\) and \(h_2\), compute \(k_1=\frac{a_2-a_1}{g}h_1\).
Hence obtain a general solution.
[k_1=k_1+\frac{b_2}{g}t ][k_2=k_2-\frac{b_1}{g}t ](\(t\) is any integer)
Substitute \(k_1\) into \(x = b_1k_1+a_1\).
[x=b_1k_1+\frac{b_1b_2}{g}t+a_1 ]Therefore
[x \equiv b_1k_1+a_1 \pmod {\operatorname{lcm}(b_1,b_2)} ]Continue merging.
Example: P4777 [Template] Extended Chinese Remainder Theorem (EXCRT)
Click to view code``` #include<bits/stdc++.h> #define XD 114514 #define MAXN 100010 #define ll long long #define int __int128 using namespace std; int n,a[MAXN],b[MAXN]; int gcd(int x,int y){ return y==0?x:gcd(y,x%y); } int lcm(int x,int y){ return x/gcd(x,y)y; } void exgcd(ll a,ll b,int &x,int &y){ if(a%b==0){ x=0,y=1; return; } exgcd(b,a%b,y,x); y-=a/bx; } ll cab_a,cab_b; int k1,k2,g,nem1,nem2,mod; void solve(int a,int b){ g=gcd(cab_b,b); if((a-cab_a)%g!=0) exit(0);//No solution exgcd(cab_b,b,nem1,nem2); k1=(a-cab_a)/gnem1; k1=(k1%(b/g)+(b/g))%(b/g);//Make k1 positive mod=lcm(cab_b,b); cab_a=((cab_bk1+cab_a)%mod+mod)%mod;//Make cab_a positive cab_b=mod; } signed main(){ cin>>n; for(int i=1;i<=n;i++) cin>>b[i]>>a[i]; cab_a=a[1],cab_b=b[1]; for(int i=2;i<=n;i++){ solve(a[i],b[i]); } cout<<cab_a%cab_b; return 0; }
Let me explain further. The general solution to \\(ax+by=\\gcd(a,b)\\) is:
\[\begin{cases} x = x + k\dfrac{b}{\gcd(a,b)} \\ y = y-k\dfrac{a}{\gcd(a,b)} \end{cases} \](\\(k\\) is any integer)
Substituting the new \\(x,y\\) into \\(ax+by=\\gcd(a,b)\\) still satisfies the equation.
Since the problem asks for the **minimal non-negative integer solution**, variables are adjusted to be positive in code.
Inclusion-Exclusion Principle
====
See the concept of sets here.
A side note, I started learning sets from the above link.
We have sets \\(A,B,C\\), find \\(|A \\cup B \\cup C|\\). The formula is:
\[|A \cup B \cup C|=|A|+|B|+|C|-|A \cap B|-|A \cap C|-|B \cap C|+|A \cap B \cap C| \]If we have \\(n\\) sets \\(P\_1,P\_2,...,P\_n\\), then:
\[|\bigcup\limits_{i=1}^n P_i|=\sum\limits_{S\subseteq[1,2,...,n]}(-1)^{|S|-1}|\bigcap\limits_{s\in S}P _ s|\]Binomial Theorem
=====
(Write on 2023.4.29)
Mainly about \\(\\dbinom{n}{m}\\).
Binomial Theorem
Lucas Theorem
=======
Definition
--
For a prime \\(p\\),
\[\dbinom{n}{m} \equiv \dbinom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor}\dbinom{n \bmod p}{m \bmod p}\pmod p \]I don't know the proof yet, here's a link QWQ.
Link
But now I know. QWQ (by 2023.7.11)
Proof
--
Before proving, prove an identity.
\[(1+x)^p \equiv 1+x^p \pmod p \](where \\(p\\) is prime)
### Proof of this identity
We know \\((1+x)^p=\\sum\\limits\_{k=0}^p \\dbinom{p}{k}x^k\\).
For \\(\\sum\\limits\_{k=0}^{p} \\dbinom{p}{k}\\), since \\(p\\) is prime, \\(\\dbinom{p}{k}\\) is a multiple of \\(p\\), i.e., \\(\\dbinom{p}{k} \\equiv 0 \\pmod p\\), because \\(\\dbinom{p}{k}=\\dfrac{p!}{k!(p-k)!}\\), and to cancel out \\(p\\), only \\(k=p\\) or \\(p-k=p\\) works, i.e., \\(k=p\\) or \\(0\\). For others, \\(p\\) appears in numerator, and since \\(p\\) is prime, denominator must contain \\(p\\) to cancel it.
So we get:
\[(1+x)^p \equiv 1 +\sum\limits_{k=1}^{p-1}\dbinom{p}{k}x^k+x^p \equiv 1+x^p \mod p \]Q.E.D.
Now prove Lucas theorem.
Let \\(n=k\_np+r\_n\\), \\(m=k\_mp+r\_m\\), so \\(\\lfloor \\dfrac{n}{p}\\rfloor=k\_n\\), \\(\\lfloor \\dfrac{m}{p}\\rfloor=k\_m\\), \\(n \\bmod p=r\_n\\), \\(m \\bmod p=r\_m\\).
\[\begin{aligned}(1+x)^n&=(1+x)^{k_np+r_n}\\&=(1+x)^{k_np}\times (1+x)^{r_n}\\&=((1+x)^p)^{k_n}\times (1+x)^{r_n}\\&\equiv (1+x^p)^{k_n}\times (1+x)^{r_n} \pmod p\\&\equiv \sum\limits_{i=0}^{k_n}\dbinom{k_n}{i}x^{ip}\times \sum\limits_{i=0}^{r_n}\dbinom{r_n}{i}x^i \pmod p\end{aligned} \]So:
\[\sum\limits_{i=0}^n\dbinom{n}{i}x^i\equiv \sum\limits_{i=0}^{k_n}\dbinom{k_n}{i}x^{ip}\times \sum\limits_{i=0}^{r_n}\dbinom{r_n}{i}x^i \pmod p \]For any integer \\(z\\), there exists \\(i,j\\) such that \\(x^z=x^{ip}x^j\\). So \\(z=ip+j\\), meaning the left side's coefficient corresponds to the right side's terms.
When the left side \\(i=m\\), the right side gives \\(i=k\_m=\\lfloor\\dfrac{m}{p}\\rfloor\\), \\(i=r\_m=m \\bmod p\\).
Then:
\[\begin{aligned}\dbinom{n}{m}x^m &\equiv\dbinom{k_n}{k_m}x^{k_mp}\times \dbinom{r_n}{r_m}x^{r_m}\pmod p \\&\equiv\dbinom{k_n}{k_m}\dbinom{r_n}{r_m}x^{k_mp}x^{r_m}\pmod p \\&\equiv\dbinom{k_n}{k_m}\dbinom{r_n}{r_m}x^{k_mp+r_m}\pmod p \\&\equiv\dbinom{k_n}{k_m}\dbinom{r_n}{r_m}x^m\pmod p \end{aligned} \]Multiply both sides by \\(x^m\\)'s inverse to get:
\[\dbinom{n}{m} \equiv \dbinom{k_n}{k_m}\dbinom{r_n}{r_m}\pmod p \]Which means:
\[\dbinom{n}{m} \equiv \dbinom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor}\dbinom{n \bmod p}{m \bmod p}\pmod p \]Q.E.D.
When \\(p\\) is not prime, we need the exLucas theorem.
exLucas theorem will be studied later. QWQ
Example
--
P3807 [Template] Lucas Theorem/Lucas Theorem
Template problem. Listening to one speech, like listening to one speech.
Direct code.
Click to view code```
#include<bits/stdc++.h>
#define XD 114514
using namespace std;
int t;
int power(int x,int y,int p){//Fast exponentiation
int ans=1;
while(y){
if(y&1) ans=1ll*ans*x%p;
x=1ll*x*x%p;
y>>=1;
}
return ans;
}
int C(int n,int m,int p){//Combination
if(n<m) return 0;
int a=1,b=1;
for(int i=1;i<=n;i++) a=1ll*a*i%p;
for(int i=1;i<=m;i++) b=1ll*b*i%p;
for(int i=1;i<=n-m;i++) b=1ll*b*i%p;
return 1ll*a*power(b,p-2,p)%p;
}
int Lucas(int n,int m,int p){//Lucas recursion
if(n<p and m<p) return C(n,m,p);
return 1ll*Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
int main(){
cin>>t;
while(t--){
int n,m,p;
cin>>n>>m>>p;
cout<<Lucas(n+m,m,p)<<'\n';
}
return 0;
}
Möbius Inversion
Möbius Inversion
Others
Other number theory problems (or maybe solutions) follow.
(Write on 2023.5.23)
P3708 Koishi's Math Problem
Interesting problem.
Upon seeing this, I thought how to transform \(f(x)\) to \(f(x+1)\) efficiently (time complexity ideally \(O(1)\)).
[f(x)=\sum\limits_{i=1}^n x \bmod i ][f(x)=\sum\limits_{i=1}^n x-\lfloor\frac{x}{i}\rfloor i ][f(x)=nx - \sum\limits_{i=1}^n \lfloor\frac{x}{i}\rfloor i ]Then:
[f(x+1)=n(x+1) - \sum\limits_{i=1}^n \lfloor\frac{x+1}{i}\rfloor i ][f(x+1)=n+nx - \sum\limits_{i=1}^n \lfloor\frac{x+1}{i}\rfloor i ]Consider changes from \(\sum\limits^{i=1}_n \lfloor\frac{x}{i}\rfloor i\) to \(\sum\limits^{i=1}_n \lfloor\frac{x+1}{i}\rfloor i\).
Only when \(i | (x+1)\), \(\lfloor\frac{x}{i}\rfloor\) increases by \(1\), contributing \(i\) to the total.
So the total increase is the sum of divisors of \(x+1\).
Therefore \(f(x+1)=f(x) + n - a_{x+1}\) (\(a_{x+1}\) is sum of divisors of \(x+1\))
Also \(f(1) = n-1\). (Evidently)
Click to view code``` #include<bits/stdc++.h> #define XD 114514 #define MAXN 1000010 using namespace std; int n,a[MAXN]; long long result; void compute(){//Preprocessing for(int i=1;i<=n;i++){ for(int j=i;j<=n;j+=i){ a[j]+=i; } } } void solve(){//Solve problem result=n-1; cout<<result<<" "; for(int i=2;i<=n;i++){ result=result+n-a[i]; cout<<result<<" "; } } int main(){ cin>>n; compute(); solve(); return 0; }
On 2023.8.12.
P2568 GCD
Find \\(\\large\\sum\\limits\_{p \\in \\text{prime}}\\sum\\limits\_{i=1}^n\\sum\\limits\_{j=1}^n\[\\gcd(i,j)==p\]\\). From \\(\\gcd(i,j)=p\\), we get \\(\\gcd(\\dfrac{i}{p},\\dfrac{j}{p})=1\\), so the original expression becomes \\(\\large\\sum\\limits\_{p \\in \\text{prime}}\\sum\\limits\_{i=1}^{\\frac{n}{p}}\\sum\\limits\_{j=1}^{\\frac{n}{p}}\[\\gcd(i,j)==1\]\\). It's similar to the expression in P2158 \[SDOI2008\] Guard Formation, so we can compute Euler's totient function linearly.
Click to view code```
#include<bits/stdc++.h>
#define XD 114514
#define MAXN 10000010
#define int long long
using namespace std;
int n;
int sum[MAXN],phi[MAXN],tot,prime[MAXN];
bool visited[MAXN];
long long result;
void compute(){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!visited[i]) prime[++tot]=i,phi[i]=i-1;
for(int j=1;j<=tot and i*prime[j]<=n;j++){
visited[i*prime[j]]=true;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}else{
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+phi[i];
}
signed main(){
cin>>n;
compute();
for(int i=1;i<=tot;i++) result+=2*sum[n/prime[i]]-1;
cout<<result;
return 0;
}