Before Reading
It's my first blog on Codeforces, so I truely don't know how to use $$$\LaTeX$$$ on it. If you have any suggestions, please write it down in the comments. I'll learn more!
And I'm keep write it know! If you like it, give me a like (and thank you for your support)！ Iy's free and you can cancel it at any time.
Now, I'm preparing for my exam at the end of the term. So I will write slower. But don't be worry, I will finish this blog! Please understand that due to the long time between each update, there may be some differences in the writing style ($$$\LaTeX$$$ and markdown) of them.
Enjoy the blog!
Congruent
Define
If $$$a,b$$$ are two integers and their difference is divisible by some natural number $$$m$$$, then $$$a$$$ is said to be congruent to $$$b$$$ with respect to the modulus $$$m$$$, or $$$a$$$ is congruent to $$$b$$$ with respect to the modulus $$$m$$$, denoted $$$a \equiv b \pmod m$$$. This means that $$$a - b = m \times k$$$ ($$$k$$$ is some integer).
For example, $$$32 \equiv 2 \pmod 5$$$, when $$$k$$$ is $$$6$$$.
For integers $$$a$$$, $$$b$$$, and $$$m$$$, $$$a$$$ and $$$b$$$ are said to be congruent in the sense of $$$\bmod m$$$ if $$$a \bmod m = b \bmod m$$$, denoted $$$a \equiv b \pmod m$$$.
It is easily obtained from the concept:
1. if $$$a \equiv b \pmod m$$$, then it is fixed that $$$\sqsupseteq k,l,c \in \mathbb{Z},a = km + c,b = lm + c$$$; 2. if $$$a \equiv b \pmod m$$$, if and only if $$$m \mid (a - b)$$$.
$$$\because a \equiv b \pmod m$$$
$$$\therefore \sqsupseteq k,l,c \in \mathbb{Z},a = km + c,b = lm + c$$$
$$$\therefore m \mid (a - b) \Rightarrow m \mid (km + c - lm - c) \Rightarrow m \mid (km - lm) \Rightarrow m \mid (k - l)m$$$
$$$The\ conclusion\ is\ valid$$$
characteristic
Self-reflexivity: $$$a \equiv a \pmod m$$$.
Symmetry: if $$$a \equiv b \pmod m$$$, then $$$b \equiv a \pmod m$$$.
Transitive: if $$$a \equiv b \pmod m,b \equiv c \pmod m$$$, then $$$a \equiv c \pmod m$$$.
Same additivity: if $$$a \equiv b \pmod m$$$, then $$$a + c \equiv b + c \pmod m$$$.
$$$\because a \equiv b \pmod m$$$
$$$\therefore \sqsupseteq k,l,\alpha \in \mathbb{Z},a = km + \alpha,b = lm + \alpha$$$
$$$\therefore a + c \equiv b + c \pmod m$$$
$$$\Rightarrow km + \alpha + c \equiv lm + \alpha + c \pmod m$$$
$$$\Rightarrow km + (a + c) \equiv lm + (a + c) \pmod m$$$
$$$The\ conclusion\ is\ valid$$$
Simultaneity: if $$$a \equiv b \pmod m$$$, then $$$a \times c \equiv b \times c \pmod m$$$;
If $$$a \equiv b \pmod m,c \equiv d \pmod m$$$, then $$$a \times c \equiv b \times d \pmod m$$$.
$$$\because a \equiv b \pmod m,c \equiv d \pmod m$$$
$$$\therefore \sqsupseteq k,l,c \in \mathbb{Z},a = km + c,b = lm + c$$$
$$$\because c \equiv d \pmod m$$$
$$$\therefore \sqsupseteq k,l,\gamma \in \mathbb{Z},c = \alpha m + \gamma,d = \beta m + \gamma$$$
$$$\therefore ac \equiv bd \pmod m$$$
$$$\Leftrightarrow (km + c)(\alpha m + \gamma) \equiv (lm + c)(\beta m + \gamma) \pmod m$$$
$$$\Leftrightarrow k\alpha m^2 + c\alpha m + c\gamma \equiv l\beta m^2 + \gamma m + c\gamma \pmod m$$$
$$$The\ conclusion\ is\ valid$$$
Does not satisfy simultaneous divisibility, but if $$$\gcd(c,m) = 1$$$, then there is $$$a \equiv b \pmod m$$$ when $$$a \times c \equiv b \times c \pmod m$$$.
$$$ac \equiv bc \pmod m$$$
$$$\Rightarrow c(a - b) \equiv 0 \pmod m$$$
$$$\Rightarrow c \% m \times (a - b) \% m = 0$$$
$$$\Rightarrow m \mid c\ or\ \ m \mid (a - b)$$$
$$$\because (m,c) = 1$$$
$$$\therefore m \mid (a - b)$$$
$$$a \equiv b \pmod m$$$
$$$The\ conclusion\ is\ valid$$$
Idempotence: if $$$a \equiv m \pmod m$$$, then $$$a^n \equiv b^n \pmod m$$$.
Certification 1
$$$\because a^n \equiv b^n \pmod m \Leftrightarrow \overbrace{a \times a \times \cdots \times a}^{a^n} \equiv \overbrace{b \times b \times b \times \cdots \times b}^{b^n} \pmod m$$$
$$$\therefore a \equiv b \pmod m$$$
$$$\because a \equiv b \pmod m$$$
$$$\therefore a \times a \equiv b \times b \pmod m\ \ conclude 6$$$
$$$\because a \times a\equiv b \times b \pmod m,a \equiv m \pmod m$$$
$$$\therefore (a \times a)\times a \equiv (b \times b)\times b \pmod m\ \ conclude 6$$$
$$$\cdots$$$
$$$The\ above\ conclusion\ can\ be\ obtained\ by\ using\ conclusion\ 6\ only\ several\ times$$$Certification 2
$$$\because \sqsupseteq k,l,c \in \mathbb{Z},a = km + c,b = lm + c$$$
$$$\therefore when b = 2, (km + c)^2 \Leftrightarrow (km)^2 + 2kmc + c^2,(lm + c)^2 \Leftrightarrow (lm)^2 + 2lmc + c^2$$$
$$$\therefore when b = 3, (km + c)^3 \Leftrightarrow (km)^3 + 3(km)^2c + 3kmc^2 + c^3,(lm + c)^3 \Leftrightarrow (lm)^3 + 3(lm)^2c + 3lmc^2 + c^3$$$
$$$\cdots$$$
$$$According\ to\ the\ quadratic\ term\ theorem,\ the\ coefficient\ expansion\ of\ the\ constant\ term\ of\ is\ c^n,\ that\ means\ (a^n) \pmod m = (a \bmod m)^n,(b^n) \bmod m = (b \bmod m)^n$$$
$$$\because a \equiv b \pmod m$$$
$$$\therefore a^n \equiv a^n \pmod m$$$
Corollary 1: $$$a \times b \pmod k = (a \bmod k)\times (b \bmod k)\bmod k$$$.
Corollary 2: If $$$\gcd(p, q) = 1$$$, $$$a \bmod p = x,a \bmod q = x$$$，则 $$$a \bmod (p \times q) = x$$$.
$$$\because \gcd(p, q) = 1,\ a \bmod p = x,a \bmod q = x$$$
$$$\therefore There\ must\ exist\ an\ integer\ s,\ t,\ makes\ a = s \times p + x,a = t \times q +x$$$
$$$\therefore s \times p = t \times q$$$
$$$\because t\ is\ an\ integer,\gcd(p, q) = 1,\ move\ q to\ the\ left$$$
$$$\therefore q \mid s,\ that\ means\ there\ is\ an\ integer\ r\ which\ can\ makes\ s = r \times q$$$
$$$\therefore a = r \times q \times p + x,\ a \bmod (p \times q) = x$$$Certification 1
$$$a \bmod q = x,a \bmod p = x$$$
$$$\therefore \sqsupseteq k,l \in \mathbb{Z},a = kq + x,b = lq + x$$$
$$$\therefore q \mid (a -x),p \mid (a -x)$$$
$$$\therefore (a -x) = cm(p, q)$$$
$$$\therefore \sqsupseteq \alpha \in \mathbb{Z},(a - x) = \alpha pq + x$$$
$$$a = \alpha pq + x$$$
$$$a \bmod pq = x$$$Certification 2
$$$\because a \bmod q = x,a \bmod p$$$
$$$\sqsupseteq k,l \in \mathbb{Z},a = kq + x = lp + x$$$
$$$\therefore kq + x = lp + x \Rightarrow kq = lp$$$
$$$\because \gcd(q,p) = 1$$$
$$$\therefore \sqsupseteq r \in \mathbb{Z},k = rp$$$
$$$\therefore a= rpq + x$$$
$$$\therefore a \bmod pq = x$$$
Prime Number
Define
A natural number greater than $$$1$$$ that is not divisible by other natural numbers is called a prime number, and conversely, a number that is not prime is called a and.
* $$$1$$$ is neither a prime nor a sum;
* $$$2$$$ is the smallest prime number and the only even prime number;
* The number of prime numbers is infinite.
Assuming that the number of prime numbers is finite, then all prime numbers can be expressed as $$$a_1,a_2,a_3,\cdots ,a_n$$$, let $$$m = a_1 + a_2 + a_3 + \cdots + a_n,p = m + 1$$$, then it is easy to prove that $$$p$$$ will not be divisible by all of the above, so that $$$p$$$ is a prime number, i.e., the assumption does not hold, and it can be obtained that the number of prime numbers is infinite.
Theorem
Fundamental Theorem of Arithmetic (Unique Decomposition Theorem)
Any positive integer greater than $$$1$$$ must be uniquely decomposable into a product of finite prime numbers as follows:
$$$N = p_1^{c_1}p_2^{c_2}p_3^{c_3} \cdots p_n^{c_n}$$$
where $$$c_i$$$ are all positive integers and $$$p_i$$$ are all primes and satisfy $$$p_1 < p_2 < p_3 < \cdots < p_n$$$.
$$$N$$$ can contain at most one factor greater than $$$\sqrt{N}$$$
If two of the factors of $$$N$$$ are greater than $$$\sqrt{N}$$$, then the multiplication of those two factors will be greater than $$$N$$$.
Decompose Prime Factors
Test Division
Enumerate from $$$2$$$ to $$$\sqrt{N}$$$, if $$$i(2 \le i \le \sqrt{N})$$$ is divisible by $$$N$$$ and $$$i$$$ is prime, then net and record the number of prime factors, and if the final number $$$n > 1$$$, then this is the prime factor of $$$N$$$ greater than $$$\sqrt{N}$$$.
#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
int n, a[N];
void decompose(int x) {
for (int i = 2; i * i <= n; i++)
while (x % i == 0) x /= i;
if (x > 1) a[x]++;
}
int main() {
scanf("%d", &n);
decompose(n);
for (int i = 1; i <= n; i++)
if (a[i]) printf("%d %d\n", i, a[i]);
return 0;
}
Time complexity: $$$O(\sqrt{n})$$$, The best-case scenario is $$$n = 2^k$$$ and $$$\log n$$$ times completion; the worst-case scenario is that $$$n$$$ is inherently prime, with time complexity $$$O(\sqrt{n})$$$.
example CF1444A Division
Problem: Find the largest positive integer $$$x$$$ such that $$$a \mid p$$$ $$$q \nmid x$$$.
Solution
When $$$q \nmid p$$$, it is clear that $$$x_{max} = p$$$.
When $$$q \mid p$$$, consider decomposing the prime factors for $$$q$$$.
This yields: $$$q = m_1^{c_1}m_2^{c_2}m_3^{c_3} \cdots m_n^{c_n}$$$.
Then, $$$x$$$ is not a multiple of $$$q$$$ if and only if there exists $$$i$$$ such that the number of times $$$m_i$$$ is greater than $$$c_i$$$ after $$$x$$$ decomposes the prime factors.
So, one can enumerate every $$$m_i$$$ such that the number of times $$$x$$$ decomposes the prime factorization of $$$m_i$$$ is $$$c_i -1$$$, and just take the maximum of all the rest. That is, if $$$t$$$ is the number of times $$$p$$$ is divisible, the optimal solution is $$$p_i^{c_i - 1} \times t$$$.
Finally, we iterate through the optimal solutions and take the maximum.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int T;
ll p, q, ans, s;
int main() {
scanf("%d", &T);
while (T--) {
scanf("%lld%lld", &p, &q);
ans = 0, s = p;
if (p % q) {
printf("%lld\n", s);
continue;
}
for (ll i = 2; i * i <= q; i++) {
if (q % i == 0) {
ll t = 1;
while (p % i == 0) p /= i, t *= i;
while (q % i == 0) q /= i, t /= i;
ans = max(ans, s / t / i);
}
}
if (q > 1) {
ll t = 1;
while (p % q == 0) p /= q, t *= q;
ans = max(ans, s / t);
}
printf("%lld\n", ans);
}
return 0;
}
You may be asking, ah this code of yours is not quite the same as what you're talking about, because the code is what I typed ahead of time.
Determination of a single prime number
The time complexity of determining a single prime is $$$O(\sqrt{n})$$$.
#include <bits/stdc++.h>
using namespace std;
int n, t;
bool prime(int x) {
if (x == 1) return 0;
for (int i = 2; i * i <= x; i++)
if (x % i == 0) return 0;
return 1;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &t);
if (prime(t)) printf("%d ", t);
}
return 0;
}
Prime Number Sieve
Echheimer's sieve method
To find all the primes in each range, start with $$$2$$$1 and remove all multiples of $$$2$$$, leaving the first number ($$$3$$$) as the second prime; then remove all multiples of $$$3$$$, and so on. Thus, we can sieve all prime numbers up to $$$n$$$.
Echidna's sieve is a sieve with a time complexity of $$$O(n\log \log n)$$$. The reason for the wasted time complexity is that the Echidna sieve sifts the same number over and over again, e.g., $$$6$$$ is sifted once at $$$i = 2$$$ and then again at $$$i = 3$$$, which wastes some of the time complexity. Therefore, a better time complexity algorithm, the linear sieve, was developed.
Rapid Linear Sieve Method
Also known as the Euler sieve method, each sum is sieved by only its minimum prime factor with a time complexity of $$$O(n)$$$.
The linear sieve method enumerates each number from smallest to largest, and will do the following:
1. if the current function is not crossed out, the number is designated as prime and the prime is recorded;
2. enumerate the recorded prime number (break if the ensemble has crossed the line)
(1) The ensemble is crossed out if the ensemble has not crossed the line;
(2) The condition $$$i \% p == 0$$$ ensures that the composite number is crossed out only by the smallest prime factor.
If $$$i$$$ is prime, the enumeration is guaranteed to be interrupted up to itself;
If $$$i$$$ is a prime, enumerate up to its own least prime break.
When $$$n = 30$$$, the linear sieve process is as follows:
$$$i = 2;\ p_2;\ v_4;\ (2 \% 2)\ break$$$
$$$i = 3;\ p_3;\ v_{6,9};\ (3 \% 3)\ break$$$
$$$i = 3;\ p_3;\ v_{6,9};\ (4 \% 2)\ break$$$
$$$i = 5;\ p_5;\ v_{10,15,25};\ (5 \% 5)\ break$$$
$$$i = 6;\ p_5;\ v_{10,15,25};\ (6 \% 2)\ break$$$
$$$i = 7;\ p_7;\ v_{14,21};\ (35 > 30)$$$
$$$i = 8;\ \ \ \ \ \ \ \ \ v_{16};\ (8 \% 2)\ break$$$
$$$i = 9;\ \ \ \ \ \ \ \ \ \ v_{18,27};\ (9 \% 3)\ break$$$
$$$i = 10;\ \ \ \ \ \ \ \ \ \ v_{20};\ (10 \% 2)\ break$$$
$$$i = 11;\ p_{11};\ v_{22};\ (33 > 30)$$$
$$$i = 12;\ \ \ \ \ \ \ v_{24};\ (12 \% 2)\ break$$$
$$$\cdots$$$
#include <bits/stdc++.h>
using namespace std;
const int N = 100000005;
int cnt;
int vis[N], prime[N];
void get_prime(int n) {
for (int i = 2; i <= n; i++) {
if (!vis[i]) prime[++cnt] = i;
for (int j = 1; 1ll * i * prime[j] <= n; j++) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}
int main() {
int n, m, k;
scanf("%d%d", &n, &m);
get_prime(n);
while (m--) {
scanf("%d", &k);
printf("%d\n", prime[k]);
}
return 0;
}
In the above code, if (i % prime[j] == o) break; is used to control that each conjunction is sifted only once.
$$$i = 2 \times 3 \times 5$$$, which sifts $$$2 \times i$$$ but not $$$3 \times i$$$. If $$$3 \times i$$$ is sieved at this point, when $$$i' = 3 \times 3 \times 5$$$, sieving $$$2 \times i'$$$ is the same as the previous sieve, i.e., if $$$i \bmod prime_j == 0$$$, it means that $$$i$$$ has a minimum prime factor $$$prime_j$$$ of its own, which is sufficient to terminate the sieve according to the principle of linear sieve.
Euler Function
Define
For a positive integer $$$n$$$, its Euler function is the number of numbers less than or equal to $$$n$$$ that are mutually prime with $$$n$$$, denoted by the letter $$$\varphi$$$.
The generalized formula:
$$$\varphi(n) = n \times \prod_{i = 1}^k (i - \frac{1}{p_i})$$$
where $$$p_1,p_2,\cdots,p_k$$$ are all prime factors of $$$n$$$ and $$$n$$$ is a positive integer.
$$$\varphi(12) = 4$$$, i.e., the number of numbers within $$$12$$$ that are mutually prime with $$$n$$$ is $$$4$$$, and there are $$$1,5,7,11$$$.
Calculate the following using the generalized formula:
$$$\varphi(12) = 12 \times (1 - \frac{1}{2}) \times (1 - \frac{1}{3}) = 4$$$.
Explanation: $$$12$$$ has prime factors $$$2,3$$$.
Characteristic
- $$$\varphi(1) = 1$$$.
- If $$$p$$$ is a prime number, then $$$\varphi(p) = p - 1$$$.
- if $$$p$$$ is a prime, then $$$\varphi(p^k) = (p - 1) \times p^{k - 1}$$$.
The Euler function is a product function: for any two positive integers $$$a,b$$$ with $$$\gcd(a,b) = 1$$$ mutually prime, $$$\varphi(a \times b) = \varphi(a) \times \varphi(b)$$$. In particular, for odd $$$n$$$, $$$\varphi(2n) = \varphi(n)$$$.
Easy to prove properties $$$1,2$$$.
Property $$$3$$$: For $$$n = p^k$$$, there are $$$p^{k - 1} - 1$$$ positive integers smaller than $$$n$$$. Of these, all those that are divisible by $$$p$$$ can be expressed as $$$p \times t$$$ of the form $$$(t = 1,2,3,\cdots,p^{k-1} - 1)$$$, and there are a total of $$$p^{k - 1} - 1$$$ numbers that are divisible by $$$p$$$ (which can't be counted as $$$p^{k - 1}$$$ because $$$p^{k - 1} \times p = n$$$), i.e., they are not mutually exclusive with $$$p^k$$$. $$$p^k$$$ mutually prime. So $$$\varphi(p^k) = p^k - 1 - (k^{k - 1} - 1) = p^k - p^{k - 1} = (p - 1) \times p^{k - 1}$$$.
Property $$$4$$$: requires the use of the Chinese Remainder Theorem, which you can skip if you haven't learned it (I'll just skip it).
Let $$$\mathbb{Z} _ n$$$ denote the mod $$$n$$$ residue class ring, then it is easy to show that $$$\forall a \forall b(\gcd(a,b)) = 1 \wedge ab \Rightarrow \mathbb{Z} _ n \cong \mathbb{Z} _ a \oplus \mathbb{Z} _ b$$$. By Pei Shu's theorem, $$$k$$$ is an invertible element in the ring $$$\mathbb{Z} _ n$$$ if and only if $$$\gcd(k,n) = 1$$$, so the number of invertible elements in the ring $$$\mathbb{Z} _ n$$$ is $$$\varphi(n)$$$ and the number of invertible elements in the ring $$$\mathbb{Z} _ a \oplus \mathbb{Z} _ b$$$ is $$$\ varphi(a)\varphi(b)$$$. Since $$$\mathbb{Z} _ n \cong \mathbb{Z} _ a \oplus \mathbb{Z} _ b$$$, $$$\varphi(n) = \varphi(a)\varphi(b)$$$.
Deformation of Euler's Function Properties
$$$p$$$ is prime if $$$n \% p = 0$$$, then $$$\varphi(n \times p) = p \times \varphi(n)$$$.
The prime factor of $$$n \times p$$$ is the same as $$$n$$$, so it is sufficient to expand $$$\varphi(n \times p)$$$ using the Euler function formula. (This article deforms some materials require $$$p$$$ to be prime, in fact, $$$p$$$ is not prime and still holds, I will not prove, I will not give a detailed proof here.)
$$$p$$$ is prime if $$$n \% p \neq 0$$$, then $$$\varphi(n \times p) = (p - 1) \times \varphi(n)$$$.
$$$p$$$ is prime and $$$n \% p \neq 0$$$, so $$$n$$$ and $$$p$$$ are mutually prime and satisfy the product function.
$$$\varphi(2n) = \varphi(n)$$$ when $$$n$$$ is an odd number.
Numbers that are mutually prime with $$$n$$$ occur in pairs and each pair sums to $$$n$$$, so $$$\varphi(n)$$$ of numbers greater than $$$2$$$ are even.
Suppose $$$\gcd(n,x) = 1,x < n,x > 2$$$, but $$$\gcd(n,n - x) = k (k > 1)$$$, which can be rewritten as $$$n = a \times k,n - x = b \times k$$$, then shifting the terms gives $$$x = n - k \times k = a \times k - b \times k = (a - b)\times k $$$, then $$$\gcd(n,x) = \gcd(ak,(a - b)k)$$$, and they have at least one convention $$$k$$$, contradicting the assumption.
Proof of Euler's Function
Euler's Function Formula
by the unique decomposition theorem:
$$$n = \prod_{i = 1}^s p_i^{a_i} = p_1^{a_1} p_2^{a_2} p_3^{a_3} \cdots p_s^{a_s}, \varphi(n) = \prod_{i = 1}^s \varphi(p_i^{a_i})(By\ property\ 4,\ the\ product\ function)$$$
$$$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \prod_{i = 1}^s p_i^{a_i - 1}(p_i - 1)(By\ property\ 3)$$$
$$$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \prod_{i = 1}^s p_i^{a_i} (1 - \frac{1}{p_i})$$$
$$$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \prod_{i = 1}^s p_i^{a_i} \times \prod_{i = 1}^s(1 - \frac{1}{p_i})$$$
$$$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = n \times \prod_{i = 1}^s \frac{p_i - 1}{p_i}$$$
$$$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = n \times \frac{p _ 1 - 1}{p _ 1} \times \frac{p _ 2 - 1}{p _ 2} \times \frac{p _ 3 -1}{p _ 3} \times \cdots \times \frac{p _ s - 1}{p _ s}$$$
The Euler function is determined only by $$$n$$$ and the prime factor, independent of the number of times.
$$$\varphi(12) = 12 \times \frac{2 - 1}{2} \times \frac{3 - 1}{3} = 4$$$
Try Division to Find the Euler Function
If the value of the Euler function is only required for one number, then it is straightforward to follow the definition and solve for it at the same time as the prime factorization.
int varphi(int n) {
int m = int(sqrt(n + 0.5));
int ans = n;
for (int i = 2; i <= m; i++) {
if (n % i == 0) {
ans /= i * (i - 1);
while (n % i == 0) n /= i;
}
}
if (n > 1) ans /= n * (n - 1);
return ans;
}
Find All Euler Function Values from $$$1$$$ to $$$n$$$
Sieve Method to Find Euler Function
If $$$i$$$ is prime, then $$$phi _ i = i - 1$$$.
In a linear sieve, each ensemble $$$m$$$ is sieved by the minimum prime factor.
Let $$$p_i$$$ be the minimal prime factor of $$$m$$$, then $$$m$$$ is sifted through $$$m = p _ j \times i$$$.
1. If $$$i \bmod p_j = 0$$$, then $$$i$$$ include all prime factors of $$$m$$$.
$$$\varphi(12) = \varphi(2 \times 6) = 2 \times \varphi(6)$$$
- If $$$m \nmid p_j$$$, then $$$\gcd(t, p_j) = 1$$$.
$$$\varphi(75) = \varphi(3 \times 25) = (3 - 1) \times \varphi(25)$$$
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int p[N], vis[N], cnt;
int phi[N];
void get_phi(int n) {
phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!vis[i]) {
p[cnt++] = i;
phi[i] = i - 1;
}
for (int j = 0; i * p[j] <= n; j++) {
int m = i * p[j];
vis[m] = 1;
if (i % p[j] == 0) {
phi[m] = p[j] * phi[i];
break;
} else phi[m] = (p[j] - 1) * phi[i];
}
}
}
int main() {
int n;
scanf("%d", &n);
get_phi(n);
for (int i = 1; i <= n; i++) printf("%d\n", phi[i]);
return 0;
}
Linear Sieve to Find Approximate Numbers and Approximate Sums
Approximate number of digits According to the unique decomposition theorem for numbers, let $$$n = p_i^{r_1} \times p_2^{r_2} \times p_3^{r_3} \times \cdots \times p_k^{r_k}$$$.
For each $$$n$$$ approximation, it must come from multiplying the above prime numbers $$$p_1 \sim p_k$$$, and by the principle of multiplication, each prime factor can be chosen from $$$0$$$ to $$$r_i$$$ which is $$$r_i + 1$$$ chosen.
The approximate number of $$$n$$$ is $$$d(n) = (r_1 + 1) \times (r_2 + 1) \times (r_3 + 1) \times \cdots \times (y_k + 1) = \prod_{i = 1}^k (r_i + 1)$$$.
The process of sieving requires saving the number of occurrences (i.e., powers) of the smallest prime factor of $$$n$$$, i.e., $$$r_1$$$.
The process of sieving requires saving the number of occurrences (i.e., powers) of the smallest prime factor of $$$n$$$, i.e., $$$r_1$$$.
$$$d_i$$$ Record the approximate number of factors of $$$i$$$;
$$$num_i$$$ Record the number of least prime factors (powers) of $$$i$$$.
Scenario-based Discussion
$$$i$$$ is a prime
$$$d_i$$$: $$$i$$$ is prime, so the only approximate factors are $$$1$$$ and itself, and the number of approximate factors is $$$2$$$;
$$$num_i$$$: $$$i$$$ is prime, the self-small prime factor is itself, and the number of digits is $$$1$$$.
$$$i$$$ and the $$$j$$$th index of the enumeration is modeled as $$$0$$$(i % prime[j] == 0)
$$$prime_j$$$ is a factor of $$$i$$$, and the unique decomposition of $$$i \times prime_j$$$ does not produce a new prime factor, it is still $$$p_1,p_2,p_3,\cdots ,p_k$$$, and $$$prime_j$$$ is enumerated from the smallest to the largest, so it must be the smallest prime factor of $$$i$$$. So the minimal prime factor power of $$$i \times prime_j$$$ becomes $$$r_1 + 1$$$, which expands by the unique decomposition theorem: $$$d_{i \times prime_j} = (1 + r_ +1) \times \cdots \times (1 + r_k)$$$.
Since the recursive process pushes out the value of $$$d_{i \times prime_j}$$$ from the known $$$d_i$$$, it is possible to transfer $$$d_i$$$ to $$$d_{i \times prime_j}$$$ using the maintained $$$num_j$$$. The transfer equation is:
.
Finding the geodesic relationship between the two, it is obvious that it is one equation divided by $$$r_1 + 1$$$ and multiplied by $$$1 + r_1 + 1$$$.
This can be converted to two-form. $$$num_{i \times prime_j} = num_j + 1$$$.
It should also be noted that $$$num_{i \times prime_j}$$$ is also shifted by adding the contribution of the least prime factor $$$prime_j$$$ that ias: $$$num_{i \times prime_j} = num_i + 1$$$.
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int prime[N], d[N], num[N];
int n, cnt;
bool st[N];
void get_prime(int n) {
d[1] = 1;
for (int i = 2; i <= n; i++) {
if (!st[i]) {
prime[cnt++] = i;
d[i] = 2, num[i] = 1;
}
for (int j = 0; i * prime[j] <= n; j++) {
st[i * prime[j]] = 1;
if (i % prime[j] == 0) {
d[i * prime[j]] = d[i] / (num[i] + 1) * (num[i] + 2);
num[i * prime[j]] = num[i] + 1;
break;
}
d[i * prime[j]] = d[i] * d[prime[j]];
// d[i * prime[j]] = d[i] * 2;
// num[i * prime[j]] = 1;
}
}
}
int main() {
scanf("%d", &n);
get_prime(n);
for (int i = 1; i <= n; i++)
printf("d[%d]=%d\n", i, d[i]);
return 0;
}
Identity
Let $$$sd_i$$$ denote the approximate sum of $$$i$$$, which follows from the Fundamental Theorem of Arithmetic:
Setting $$$n = p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} \times \cdots \times p_k^{a_k}$$$, it is known that the approximation of $$$p_1^{a_1}$$$ is $$$p_1^0,p_1^1,p_1^2,\cdots,p_1^{a_1}$$$.
Similarly, the approximation of $$$p_k^{a_k}$$$ is $$$p_k^0,p_k^1,p_k^2,\cdots,p_k^{a_k}$$$.
In fact, the approximate number of $$$n$$$ is obtained by multiplying the approximate number of each of $$$p_1^{a_1},p_2^{a_2},\cdots,p_k^{a_k}$$$ by one of the approximate number of each of them, and it can be seen that there are $$$(\alpha_1 + 1) \times (\alpha_1 + 1) \times (\alpha_1 + 1) \times \times \times \times cdots \times (\alpha_1 + 1)$$$ The number of picks, i.e., the number of approximations.
By the principle of multiplication they sum to:
Let $$$num_i$$$ denote one of the minimal prime factors: $$$num_i = p_1^0 + p_1^1 + p_1^2 + \cdots + p_1^{r_1}$$$.
$$$i$$$ is a Prime Number
$$$i$$$ is a prime number whose approximate numbers are only $$$1$$$ and itself, and whose approximate sum is $$$i + 1$$$; the prime factorization can only be decomposed as follows, $$$sd_i = i_0 + i_1 = i + 1$$$.
The enumerated prime number $$$prime_j$$$ is not $$$0$$$, i.e., $$$prime_j$$$ is not divisible by $$$i$$$.
In the following discussion, $$$p_j$$$ will be used instead of $$$prime_j$$$.
There was no $$$p_j$$$ item in $$$i \times p_j$$$, but this item was added:
$$$\because sd_i = (p_1^0 + p_1^1 + p_1^2 + \cdots + p_1^{r_1}) \times (p_2^0 + p_2^1 + p_2^2 + \cdots + p_2^{r_2}) \times \cdots \times (p_k^0 + p_k^1 + p_k^2 + \cdots + p_k^{r_k})$$$
$$$also,\ \because sd_{i \times p_j} = (p_1^0 + p_1^1 + p_1^2 + \cdots + p_1^{r_1}) \times (p_2^0 + p_2^1 + p_2^2 + \cdots + p_2^{r_2}) \times \cdots \times (p_k^0 + p_k^1 + p_k^2 + \cdots + p_k^{r_k})$$$
Because $$$i \% p_j \neq 0$$$, so $$$i$$$ does not contain $$$p_j$$$ as a prime, then the prime factorization in $$$i \times p_j$$$ can decompose one more $$$p_j$$$ on top of the original $$$p_1,p_2,\cdots,p_k$$$, so when solving for $$$sd_{i \times p_j}$$$, you need more $$$\times (p_j^0 + p_j^1)$$$. so in finding $$$sd_{i \times p_j}$$$, more $$$\times (p_j^0 + p_j^1)$$$ are needed.
$$$\because p_j\ is\ a\ prime\ number$$$
$$$\therefore sd_{p_j} = p_j^0 + p_j^1$$$
$$$\therefore sd_{i \times p_j} = sd_i \times sd_{p_j}\ (product\ function)$$$
Update $$$num_{i \times p_j}$$$ at the same time:
$$$num_{i \times p_j} = num_{p_j} = p_j^0 + p_j^1 = p_j + 1$$$.Since the prime factors are enumerated from smallest to largest, then the smallest prime factor of $$$i \times p_j$$$ is $$$p_j$$$, and $$$num_{i \times p_j}$$$ should be equal to $$$num_{p_j}$$$.
The prime number $$$p_j$$$ enumerated by $$$i \%$$$ is $$$0$$$, i.e., $$$i \% p_j == 0$$$.
Then the first term in $$$sd_{i \times p_j}$$$ is $$$num_{i \times p_j}$$$.
Isoperimetric series morphing techniques:
$$$1 + p_i + p_i^2 + \cdots + p_i^{r_1}$$$, it can change to: $$$1 + p_i + p_2^i + \dots + p_i^{r_i} + p_i^{r_i + 1}$$$, Then just multiply all by $$$p_i$$$ and add $$$1$$$.
$$$(1 + p_i +p_2^i + \cdots + p_i^{r_i}) \times p_i + 1 = 1 + p_i + p_2^i + \cdots + p_i^{r_i} + p_i^{r_i + 1}$$$Conclude: $$$num_{i \times p_j} = num_i \times + 1$$$
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 10005;
bool st[N];
int n, cnt;
int num[N], sd[N], prime[N];
void get_prime (int n) {
sd[1] = 1;
for (int i = 2; i <= n; i++) {
if (!st[i]) {
prime[cnt++] = i;
sd[i] = num[i] = i + 1;
}
for (int j = 0; prime[j] * i <= n; j++) {
st[i * prime[j]] = 1;
if (i % prime[j]) {
sd[i * prime[j]] = sd[i] * sd[prime[j]];
num[i * prime[j]] = prime[j] + 1;
} else {
sd[i * prime[j]] = sd[i] / num[i] * (num[i] * prime[j] + 1);
num[i * prime[j]] = num[i] * prime[j] + 1;
break;
}
}
}
}
int main() {
scanf("%d", &n);
get_prime(n);
for (int i = 1; i <= n; i++)
printf("sd[%d]=%d\n", i, sd[i]);
return 0;
}
Euler's Theorem (Fermat's Little Theorem)
Remainder Category
Given a positive integer $$$n$$$, divide all integers into $$$n$$$ classes according to the residue $$$r \in [0,n - 1]$$$ mod $$$n$$$, each of which is denoted by $$$C_r = nx + r$$$, and the set of such numbers is a residue class mod $$$n$$$.
$$$n = 5,r = 3$$$, then $$$C_3 = 5x + 3$$$ is a residue class of mode 5$.
Complete residue classes
Given a positive integer $$$n$$$, there are $$$n$$$ different residue classes with one element in each, for a total of $$$n$$$ numbers, which form a completely new set, which is said to be a complete residue family of mode $$$n$$$.
$$$n = 5$$$, then $$${0,1,2,3,4}$$$ is a complete residue family of mode $$$5$$$, and $$$5,1,7,8,9$$$ is also a complete residue family of mode $$$5$$$.
Simplified residue system
Given a positive integer $$$n$$$, there are $$$\varphi(n)$$$ different residue classes modulo $$$n$$$ of residues $$$r$$$ and $$$b$$$ of mutual quality, take one element from each of these $$$\varphi(n)$$$ residue classes, there are a total of $$$\varphi(n)$$$ numbers, and form a new set of these numbers, which is known as the simplicial residue family of modulus $$$n$$$.
$$$n = 5$$$, then $$${1,2,3,4}$$$ is a simplicial residue family mod $$$5$$$, and $$$n = 10$$$, then $$${1,3,5,9}$$$ is a simplicial residue family mod $$$10$$$.
Clearly, all books in the simplified residue system of module $$$n$$$ are mutually prime with $$$n$$$.
Euler's theorem.
The $$$m$$$ of a modulus can be a meromorphic number.
If $$$\gcd(a,m) = 1$$$, then $$$a^{\varphi(m)} \equiv 1 \pmod m$$$.
In particular, when $$$m$$$ is prime, in agreement with Fermat's Little Theorem.
$$$n = 3,m = 4$$$, then $$$s^{\varphi(4)} \equiv 3^2 \equiv 1 \pmod 4$$$.
$$$n = 3,m = 5$$$, then $$$3^{\varphi(5)} \equiv 3^4 \equiv 1 \pmod 5$$$.
Certification
Construct a series mutually prime with $$$m$$$ and proceed as follows:
Let $$$r_1,r_2,r_3,\cdots,r_{\varphi(m)}$$$ be a simplicial residue system in the sense of mod $$$m$$$, then $$$ar_1,ar_2,ar_3,\cdots,ar_{\varphi(m)}$$$ is also a simplicial residue system in the sense of mod $$$m$$$.Since $$$a$$$ and $$$m$$$ are mutually prime, $$$r_1,r_2,r_3,\cdots,r_{\varphi(m)}$$$ is also mutually prime with $$$m$$$.
So $$$r_1 \times r_2 \times r_3 \times \cdots \times r_{\varphi(m)} \equiv ar_1 \times ar_2 \times ar_3 \times \cdots \times ar_{\varphi(m)} \equiv a^{\ varphi(m)} \times r_1 \times r_2 \times r_3 \times \cdots \times r_{\varphi(m)} \% m$$$, which can be approximated by removing the set $$$r_1 \times r_2 \times r_3 \times \cdots \times r_{\varphi(m) }$$$ This set.
** When $$$m$$$ is prime, since $$$\varphi(m) = m - 1$$$, substituting in Euler's theorem yields Fermat's Little Theorem. **
Fermat's Little Theorem
If $$$m$$$ is prime, for any number $$$a$$$, there is $$$a^m = a \pmod m$$$.
Specially, if $$$m$$$ is prime and the integer $$$a$$$ is not a multiple of $$$m$$$ (i.e., $$$\gcd(a,m) = 1$$$), then $$$a^{m - 1} \equiv 1 \pmod m$$$.
Lemma 1 (Identical divisibility)
If $$$a,b,c$$$ are any three integers, $$$m$$$ is a positive integer and $$$m$$$ and $$$c$$$ are mutually prime (after which $$$(m,c) = 1$$$ will be written), then when $$$ac \equiv bc \pmod m$$$, there is $$$a \equiv b \pmod m$$$.
It follows that $$$(a-b)c \equiv 0 \pmod m$$$
Since $$$(m,c) = 1$$$, $$$(a - b)$$$ is a multiple of $$$m$$$, i.e., $$$a - b \equiv 0 \pmod m$$$.
By congruence of congruence, we get $$$a \equiv b \pmod m$$$.
Lemma 2
$$$m$$$ is an integer greater than $$$1$$$, $$$a$$$ is an integer and $$$(m,a) = 1$$$, if $$$b_i(i \in [1,m])$$$ is a complete residue system modulo $$$m$$$, then $$$a \times b_i(i \in [1,m])$$$ is also a complete residue system modulo $$$m$$$.
If there exist two integers $$$a \times b_i,a \times b_j$$$ congruent to each other, then $$$s \times b_i \equiv a \times b_j \pmod m$$$.
By Lemma 1, $$$b_i \equiv b_j \pmod m$$$.
contradicts the original definition, so there are no two integers $$$a \times b_i,a \times b_j$$$ congruent to each other.
So $$$a \times b_i (i \in [1,m])$$$ is a complete residue system of mod $$$m$$$.Invoke a property:
Let a prime number be $$$p$$$ and we take a number $$$a$$$ that is not a multiple of $$$p$$$.
Construct a sequence: $$$A = 1,2,3,\cdots,p-1$$$ which has the property:
$$$\prod_{i = 1}^{p - 1} A_i = \prod_{i = 1}^{p - 1} (A_i \times a) \pmod p$$$.$$$\because \gcd(A_i,p) = 1,\gcd(A_i \times a,p) = 1$$$ (both complete residual systems of $$$A$$$)
$$$\text{again } \because \text{every }A_i \times a \pmod p \text{ is unique and }A_i \times a \pmod p < p$$$
$$$\therefore \text{every }A_i \times a \text{ corresponds to }A_i$$$
Let $$$f = (p - 1)! $$$, then $$$f \equiv a \times A_1 \times a \times A_2 \times a \times A_3 \times \cdots \times A_{p - 1} \pmod p$$$.
$$$\therefore a^{p - 1} \times f \equiv f \pmod p$$$$$$a^{p - 1} \times f \equiv f \pmod p$$$ in the proof of the above property, and because $$$\gcd(f,p) = 1$$$, $$$a^{p - 1} \equiv 1 \pmod p$$$. Proven.
