Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

Some useful conclutions for some naive algorithms to solve number theory problem

Revision en29, by zhengqingyuan, 2024-09-22 05:40:38

Here are some useful conclutions for naive algorithms to solve number theory problem,I hope you can know something about it and solve number theory problems more easily.

1.The number of prime factors of an integer

It's sure that the number of prime factors of an integer is very small,and an integer v can be the product of at most log2(v) primes (2k the worst).This can be used for bruteforce and State compression.

Thanks AkiLotus to remind me that for the number of distinct prime factors of a integer w(n),ni=1w(n) is O(nloglogn).

example:510D.

2.The number of factors of an integer

First of all,ni=1d(n)=ni=1[ni]nlnn.

Then I've found out that the number of factors of an integer(d(n)) is usually small,and to make sure,I made a code to get the maxinum number of the number of factors,and get:

  1. For n104,max;
  2. For n \le 5 \times 10 ^ 4,\max \operatorname{d}(n) <= 100;
  3. For n \le 10 ^ 5,\max \operatorname{d}(n) <= 128;
  4. For n \le 2 \times 10 ^ 5,\max \operatorname{d}(n) <= 160;
  5. For n \le 3 \times 10 ^ 5,\max \operatorname{d}(n) <= 180;
  6. For n \le 5 \times 10 ^ 5,\max \operatorname{d}(n) <= 200;
  7. For n \le 10 ^ 6,\max \operatorname{d}(n) <= 240;
  8. For n \le 5 \times 10 ^ 6,\max \operatorname{d}(n) <= 384;
  9. For n \le 10 ^ 7,\max \operatorname{d}(n) <= 448;

So if your solution of a problem is \operatorname{O}(n\max \operatorname{d}(a_i)) or \operatorname{O}(\sum \operatorname{d}(a_i)),it might be correct because for a_i \le 10 ^ 7,it's sure that \operatorname{d}(a_i) \le 500.

examples:

3.Euler's Function: \operatorname{O}(\log_2 n) times to 1.

It's sure that \phi(n) \le \frac{n}{2} for 2 | n,and 2 | \phi(n) for n > 1.So if you use operation x = \phi(x) for x = n initially,it will become 1 in \operatorname{O}(\log_2 n) times.

example:

4.Prefixes: \operatorname{O}(\log_2 n) distinct prefix great common diverse/and/or

Thanks Ghulam_Junaid and Timosh to remind me about the feature.

For \gcd(a_1,a_2,...,a_k),We can add a new integer a_{k + 1} and found:

  • If \gcd(a_1,a_2,...,a_k) | a_{k + 1},it's sure that \gcd(a_1,a_2,...,a_k,a_{k + 1}) = \gcd(a_1,a_2,...,a_k).
  • Otherwise,\gcd(a_1,a_2,...,a_k,a_{k + 1}) \le [\frac{\gcd(a_1,a_2,...,a_k)}{2}].

So there are at most \log_2 n distinct prefix great common diverse.

For operator and or or,every integers can be written by \log_2 n digits,and:

  • For operator and,the number of "1" in the digits decreases;
  • And for operator or,the numbr of "1" increases;

So there are at most \log_2 n prefixes and suffixes.

example:

5.At most [2\sqrt{n}] distinct integers of [\frac{n}{i}],1 \le i \le n.

Known as number theory chunking in public,we can proof that [\frac{n}{i}] = [\frac{n}{[\frac{n}{i}]}],and then split [1,n] to \operatorname{O}(\sqrt n) sections like [l,r = [\frac{n}{l}]],it's really useful while calculating \sum_{i = 1}^n \operatorname{f}([\frac{n}{i}]) or it's easy to consider several integer v_1,v_2,...,v_k together when [\frac{n}{v_i}],1 \le i \le k is the same.

example:

Last:written in the end:

I would like to thank:

Tags number theory, brute force, maths

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en33 English zhengqingyuan 2024-09-30 08:21:37 58 Tiny change: '/D)\n- [20' -> '/D)\n- [2005D](https://mirror.codeforces.com/contest/2005/problem/D)\n- [20'
en32 English zhengqingyuan 2024-09-27 09:54:33 58
en31 English zhengqingyuan 2024-09-27 08:33:12 390
en30 English zhengqingyuan 2024-09-22 16:01:05 58
en29 English zhengqingyuan 2024-09-22 05:40:38 58
en28 English zhengqingyuan 2024-09-21 16:31:51 92
en27 English zhengqingyuan 2024-09-21 15:59:13 20
en26 English zhengqingyuan 2024-09-21 15:57:49 118
en25 English zhengqingyuan 2024-09-21 15:50:08 144
en24 English zhengqingyuan 2024-09-21 06:36:44 63
en23 English zhengqingyuan 2024-09-21 06:07:56 2 Tiny change: 'conclution for naive' -> 'conclutions for naive'
en22 English zhengqingyuan 2024-09-20 11:02:07 117
en21 English zhengqingyuan 2024-09-20 10:59:30 18
en20 English zhengqingyuan 2024-09-20 10:58:55 437
en19 English zhengqingyuan 2024-09-20 10:45:05 12 Tiny change: 'er:Timosh]to remind ' -> 'er:Timosh] to remind '
en18 English zhengqingyuan 2024-09-20 10:44:52 10 Tiny change: 'ser:Timosh,2024-9-20]to remind' -> 'ser:Timosh]to remind'
en17 English zhengqingyuan 2024-09-20 10:44:29 10 Tiny change: 'ser:Timosh]to remind' -> 'ser:Timosh,2024-9-20]to remind'
en16 English zhengqingyuan 2024-09-20 10:37:09 29
en15 English zhengqingyuan 2024-09-20 10:35:51 2 Tiny change: 'd}(n) <= 68$;\n2. For' -> 'd}(n) <= 64$;\n2. For'
en14 English zhengqingyuan 2024-09-20 10:29:16 397
en13 English zhengqingyuan 2024-09-20 10:11:11 2 Tiny change: 'on diverse.\n- [user:' -> 'on diverse;\n- [user:'
en12 English zhengqingyuan 2024-09-20 10:10:58 394
en11 English zhengqingyuan 2024-09-20 08:45:40 20 Tiny change: 'v)$ primes.This can ' -> 'v)$ primes ($2 ^ k$ the worst).This can '
en10 English zhengqingyuan 2024-09-20 08:38:08 1 Tiny change: 'e to thanks:\n\n- [us' -> 'e to thank:\n\n- [us'
en9 English zhengqingyuan 2024-09-20 08:37:56 887
en8 English zhengqingyuan 2024-09-20 08:20:32 23
en7 English zhengqingyuan 2024-09-19 11:52:50 5 Tiny change: '{O}(\log_2(v))$ times t' -> '{O}(\log_2 n)$ times t'
en6 English zhengqingyuan 2024-09-19 10:15:54 484 (published)
en5 English zhengqingyuan 2024-09-19 09:47:36 2 Tiny change: 'or $\operaotrname{O}(\' -> 'or $\operatorname{O}(\'
en4 English zhengqingyuan 2024-09-19 09:47:22 20
en3 English zhengqingyuan 2024-09-19 09:46:32 17
en2 English zhengqingyuan 2024-09-19 09:45:57 7 Tiny change: 'ox n \ln n\n\nI've found' -> 'ox n \ln n$.\n\nThen I've found'
en1 English zhengqingyuan 2024-09-19 09:45:35 1816 Initial revision (saved to drafts)