Divisible theory:

  • Unique decomposition theorem, for a composite number, there is only one prime decomposition. Application in algorithm complexity estimation, factor number calculation. The number of prime factors is O(L O gn) O(logn) O(logn) The number of level factors is O(n 3) O(\ SQRT [3]{n}) O(3N) ~ O(n) O(\ SQRT {n}) O(n) level
  • If a number is divisible by a group of numbers, the number is called the common divisor of those numbers.

Pei shu theorem

  • For a,b a,b a,b, there exists x,y x,y x,y such that ax+by=gcd(a,b) ax+by= GCD (a,b) ax+by= GCD (a,b)
  • If b is 0, b is 0, and b is 0, let’s say x is 1,y is 0, x is 1,y is 0, x is 1,y is 0
  • g c d ( a , B) = ax+by = by + (a % b + a b ∗ b) x = b (y + a b ∗ x) + a % b x GCD (a,b) = AX +by = By + (a \ % b + \ frac {a} {b} * b) x = b (y + \ frac {a} {b}) * x + a \ % b * x the GCD (a, b) = ax + by = by + x (a % b + ba ∗ b) = b (y + ba ∗) x + a % b ∗ x

Congruence theory

The remaining categories:

  • Divide Z, Z, Z into M, M, M disjoint sets by the remainder divided by M, M, M
  • For example, if the remainder is a(0≤a
  • Call this set [a], a [a], a [a], a [a], where a is a representative element
  • [a] [a] [b] [b] [b] [b] [b] [a] [b] [b] [b] [a] [b] [b] [b] [a] [b] [b] [b] [a] [b] [b] [b] [a] [b] [b] [a] [b] [b] [b] [a] [b] [b] [b] [a] [b] [b] [b] [a] [b] [b] [b]
  • So we can put the description in the rest class

Euler’s theorem

  • We define φ(n) \varphi (n) φ(n) as the number of mutually essential numbers between 1 n 1 and n 1 n

  • Have a phi (n) ≡ 1 (m o d n), g c d (a, n) = 1 a ^ {\ varphi (n)} (mod n) ≡ 1, GCD (a, n) = 1 a phi (n) ≡ 1 (modn), the GCD (a, n) = 1

  • For example 57≡5(M od7),34≡1(M od10) 5^7 ≡5(mod7),3 ^4 ≡1(MOD 10) 57≡5(mod7),34≡1(mod10)

  • P_1 ^{e_1}+p_2^{e_2}+ p_2^{e_2}+… p_1^{e_1}+p_2^{e_2}+… +p_k^{e_k}=\prod_{i=1}^kp_i^{e_i} n=p1e1+p2e2+… + pkek = ∏ kpiei I = 1

  • The phi (n) = ∏ I = 1 k (p I – 1) p I e I \ varphi (n) = \ prod_ {I = 1} ^ k (p_i – 1) p_i ^ {e_i} phi (n) = ∏ I = 1 k piei (PI – 1)

  • A M ≡ {a m m< φ (n) a (m m o d φ (n)) + φ (n) m ≥ φ (n) a^m ≡ \begin{cases} A ^m & m<\varphi (n) \ \ a ^ {mod (m \ varphi (n)) + \ varphi (n)} & m \ geq \ varphi (n) \ end am ≡ {{cases}

    Ama (mmod phi (n)) + phi (n) m < from m p (n) (n)

  • You just have to consider the standard decomposition of A, A, a, p, p that is not mutually compatible with n, n, n

inverse

  • To introduce something like reciprocal into number theory
  • P p p is not 0 0 0, is there q q q such that P q ≡ 1 (m o d m)? Pq ≡ 1 (mod M)? Pq ≡ 1 (modm)?
  • Exists when p,m p, M p,m are mutually prime (known from Euler’s theorem)
  • Fast power calculation Q ≡pφ(m)−1(modm) Q ≡p ^{\varphi (m)-1} (modm) q≡pφ(m)−1(modm)
  • Since m m m is a prime number p p p p in many cases, the power p−2, p-2, p−2 is sufficient
  • The extended Euclidean algorithm can also be calculated
  • What if I ask for more than one? I can recurse linearly, let’s say p=k, q+r, p=kq+r, p=kq+r, Then kq+r≡0(mod p)⟺k − 1 ≡qr − 1 (mod p) kq+r≡0(mod p)⟺k^{-1}≡qr^{-1}(mod p) Kq + r ≡ 0 (modp) ≡ ⟺ k – 1 qr – 1 (modp)

Congruence equation

Linear congruence equation

  • Consider ax≡b(modm) Ax ≡b(modm) Ax ≡b(modm)
  • A x−my=b ax−my=b ax−my=b
  • It is solved by extended Euclidean algorithm
  • Note: there is no solution/one solution/many solutions

Congruence system

  • A number of congruences are given to solve the equations
  • Firstly, each congruence formula is solved independently
  • Modulo pairwise mutual quality: The Chinese remainder theorem, combined in a manner similar to Newtonian interpolation
  • There are modules that are not mutual: the last modules are their least common multiples, which are combined pally with extended Euclidean
  • Of course, there is no solution/one solution/many solutions

Equation of higher order congruence

  • X K ≡a(modm) x^ K ≡a(modm) xk≡a(modm)
  • A s≡1(modm) A ^s ≡1(modm) as≡1(modm)
  • K s≡0(modφ(m)) ks≡0(mod \varphi (m)) ks≡0(modφ(m))
  • Note: there is no solution/one solution/many solutions

Number theory partitioned

A few lemma

  • A bc = a bc \frac{\frac{a}{b}}{c}=\frac{a}{BC} CBA =bca
  • Of all the I I =k \frac{n}{I}=k in=k, the largest is n k \frac{n}{k} kn

Divide by the number of quotient

  • Consider n 1, 2 n, n 3,…., n n \ frac {1}, {n} \ frac {n} {2}, \ frac {n} {3},… ,\frac{n}{n} 1n,2n,3n,… ,nn
  • Example: n=10 n=10 1,2,3,5,10 1,2,3,5,10 1,2,3,5,10
  • If k2≤n< K (k+1) k^2 ≤ N
  • K (k+1)≤n<(k+1)2 K (k+1)≤n<(k+1) ^ 2 When k(k+1)≤n<(k+1)2, there are 2k, 2k, 2k
  • The different values are about O(n) O(\ SQRT n) O(n)

In addition to business value

  • Ascending order n 1, 2 n, n 3,…., n n \ frac {1}, {n} \ frac {n} {2}, \ frac {n} {3},… ,\frac{n}{n} 1n,2n,3n,… , different values in nn
  • Straight ahead 1, 2… , k 1, 2… K, 1, 2,… ,k
  • Rear n k, n k – 1, n, k – 2,…., n. 1 \ frac {n} {k}, \ frac {n}} {k – 1, \ frac {n} {2} k,… , \ frac {n} {1} kn, k – 1 n, k – 2 n… ,1n
  • According to lemma 2, 2, 2, O(1), O(1), O(1)
  • N k \frac{n}{k} kn = n k \frac{n}{k} kn
  • partitioned
for (int l = 1, r; l <= n; l = r + 1) { r = n / (n / l); ans += ... ; }Copy the code

Multiplicative function

  • We call f:Z+→C f:Z ^+ →C f:Z+→C a number theoretic function
  • The product function ∀ A, B, G C D (a, B) = 1 ∀ A, B, The GCD (a, b) = 1 ∀ a, b, the GCD (a, b) = 1 f f (a) (b) = f (a, b) f f (a) (b) = f (ab) f f (a) (b) = f (ab)
  • Complete product function f (a) f (b) = f (a, b) f (a) f (b) = f (ab) f (a) (b) f = f (ab)
  • So obviously f of 1 is equal to 1, f of 1 is equal to 1
  • The euler function phi (n) = ∑ I = 1 n g d c (I, n) = 1] phi (n) = \ sum_ {I = 1} ^ n [the GCD (I, n) = 1] phi (n) = ∑ I = 1 n [the GCD (I, n) = 1]
  • Mobius function (n) = (1 -) k o r u (n) = 0 (1) ^ kor0 mu (n) = (1 -) kor0
  • Meta function e(n)=[n=1] E (n)=[n=1] e(n)=[n=1]
  • Identity function 1(n)=1, 1(n)=1
  • Power function I dk(n)=nk ID ^k(n) =n ^k IDk (n)=nk
  • Sigma divisor function k (n) = ∑ d ∣ n d k \ sigma_k (n) = \ sum_ | n} {d d ^ k sigma k (n) = ∑ d ∣ the NDK

Linear screen or Euler screen

  • Recall the sieving method O(n L O gn) O(nlogn) O(nlogn) O(nlogn) in elementary school, in which each number is accessed by its factors
  • In the process, each number is accessed once by its factors, and each number is only accessed 1, 1, 1, so O(n) O(n) O(n)
  • The value of the product function can be obtained by using a linear sieve, considering the relationship between f(pn) f(p^n) f(pn) and f(P n−1) f(P ^{n-1}) f(pn−1)

C o d e : Code: Code:

if (i % pri[j] == 0)
{
    miu[i * pri[j]] = 0;
    phi[i * pri[j]] = phi[i] * pri[j];
    break;
}
else
{
    miu[i * pri[j]] = -miu[i];
    phi[i * pri[j]] = phi[i] * (pri[j]- 1);
}
Copy the code
  • Auxiliary arrays can be introduced in the calculation process
  • D, d, d is the number of factors, c, c, c is the minimum factor index

C o d e : Code: Code:

if (i % pri[j] == 0)
{
    c[i * pri[j]] = c[i] + 1;
    d[i * pri[j]] = d[i] / (c[i] + 1) * (c[i] + 2);
    break;
}
else
{
    c[i * pri[j]] = 1;
    d[i * pri[j]] = d[i] * 2;
}
Copy the code

Dirichlet convolution

  • Define arithmetic function between operations, (f) ∗ g (n) = ∑ I j (j) = n (I) f g * g (f) (n) = \ sum_ {ij = n} f (I) g (j) (f) ∗ g (n) = ∑ ij nf (I) = g (j)
  • It’s commutative and associative
  • Dirichlet convolution for two number theory functions with known values, consider the sieving of O(n L O gn) O(nlogn) O(nlogn) O(nlogn), adding up the contribution of each factor of N n n to it.
  • F =μ∗μ f= \mu ∗ \mu f=μ∗μ is calculated using a linear sieve

C o d e : Code: Code:

if (i % pri[j] == 0)
{
    miu[i * pri[j]] = 0;
    m[i * pri[j]] = i / pri[j] % pri[j] == 0 ? 0 : m[i / pri[j]];
    break;
}
else
{
    miu[i * pri[j]] = -miu[i];
    m[i * pri[j]] = 2 - * m[i];
}
Copy the code
  • F =μ∗φ f= \mu ∗ \varphi f=μ∗φ is calculated using a linear sieve
if (i % pri[j] == 0)
{
    mp[i * pri[j]] = i / pri[j] % pri[j] == 0 ? mp[i] * pri[j] : mp[i / pri[j]] * (pri[j] - 1) * (pri[j] - 1);
    break;
}
else
{
    mp[i * pri[j]] = mp[i] * (pri[j] - 2);
}
Copy the code

Du teach screen

  • S(n) = ∑ I =1 nf(n) S(n) = \sum_{I =1}^ NF (n) = \sum_{I =1}^nf(n) S (n) = ∑ I = 1 nf (n)
  • Find a g g g (n) (n) (n) makes the ∑ (f) ∗ g (n) \ sum (n) ∑ * g (f) (f) ∗ g (n) good try to calculate the ∑ ∑ k = 1 n I j g (I) = k f (j) = ∑ ∑ I = 1 n J = 1 n I g (I) f (j) = ∑ I = 1 n g (I) S (n) I \ sum_ {k = 1} ^ n \ sum_} {the ij = k g (I) (j) = f \sum_{i=1}^n\sum_{j=1}^{\frac{n}{i}}g(i)f(j)=\sum_{i=1}^{n}g(i) S(\frac{n}{i}) N ∑ ∑ k = 1 ij kg (I) = f (j) = ∑ ∑ I = 1 n j ing (I) = 1 f (j) = ∑ I = 1 ng (I) S (in)
  • Number theory partition + memorization G (1) S (n) = ∑ I = 1 n (f ∗ g) (I) − ∑ I = 2 n g (1) S (n I) G (1) S (n) = \ sum_ {I = 1} ^ n * g (f) (I) – \ sum_ {2} I = ^ ng (1) S (\ frac {n} {I}) g (1) S (n) = ∑ I = 1 n ∗ g (f) (I) – ∑ I = 2 ng (1) S (in)
  • Assumption of g (n) (n) g g (n) and (f) ∗ g (n) (f) * g (n) (f) ∗ g (n) the sum of linear, Directly using the du teach screen T (n) O (n 3/4) T (n) to O (n ^ {3/4}) T (n) O (n3/4), Two-thirds linear sieve first before O (n) O (n ^ two-thirds {}) O (n2/3), T (n) O (n) two-thirds of T (n) to O (n ^ two-thirds {}) T (n) O (n2/3)
  • M (n) n = ∑ I = 1 mu (I) = 1 – ∑ I n = 2 M (n) I M (n) = \ sum_ {I = 1} ^ n \ mu (I) = 1 – \ sum_ {2} I = ^ nM (\ frac {n} {I}) M (n) n = ∑ I = 1 mu (I) = 1 – ∑ I = 2 nm (in)
  • ϕ (n) = ∑ I = 1 n ϕ (I) = n (n + 1) 2 – ∑ I = 2 n ϕ (n) I \ phi (n) = \ sum_ {I = 1} ^ n \ phi (I) = \ frac {n (n + 1)} {2} – \ sum_ {2} I = ^ n \ phi (\ frac {n} {I}) ϕ (n) = ∑ I = 1 n ϕ (I) = 2 n (n + 1) – ∑ I = 2 n ϕ (in)
  • N φ (I) = n (n + 1) (2 n + 1) 6 − ∑ I = 2 n I B (n I) B (n) = \ sum_ {I = 1} ^ n \ varphi (I) = \ frac {n (n + 1) (2 n + 1)} {6} – \ sum_ {2} I = ^ niB (\ frac {n} {I}) B (n) = ∑ I = 1 n phi (I) = 6 n (n + 1) (2 n + 1) – ∑ I = 2 niB (in)

At present contact with these, later and new to supplement.