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$$$
$$$\therefore 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 \text{或}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: $$$d_{i \times prime_j} = d_i \div (num_i + 1) \times (num_i + 1 + 1)$$$.
$\begin{cases} d(i) = (r_1 + 1) \times (r_2 + 1) \times \cdots \times (r_k + 1)\ d(i \times prime_j) = (1 + r_1 + 1) \times \cdots \times (1 + r_k) \end{cases}$
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$$$.
