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

Правка en6, от zhengqingyuan, 2024-09-19 10:15:54

Here are some useful conclution 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 intelliger

It's sure that the number of prime factors of an intelliger is very small,and an intelliger $$$v$$$ can be divided into $$$\log_2(v)$$$ primes.This can be used for bruteforce and State compression.

example:510D.

2.The number of factors of an intelliger

First of all,$$$\sum_{i = 1} ^ n \operatorname{d}(n) = \sum_{i = 1} ^ n [\frac{n}{i}] \approx n \ln n$$$.

Then I've found out that the number of factors of an intelliger($$$\operatorname{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 $$$n \le 10 ^ 4,\max \operatorname{d}(n) <= 68$$$;
  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(v))$$$ 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:906D.

Теги number theory, brute force, maths

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en33 Английский zhengqingyuan 2024-09-30 08:21:37 58 Tiny change: '/D)\n- [20' -> '/D)\n- [2005D](https://codeforces.me/contest/2005/problem/D)\n- [20'
en32 Английский zhengqingyuan 2024-09-27 09:54:33 58
en31 Английский zhengqingyuan 2024-09-27 08:33:12 390
en30 Английский zhengqingyuan 2024-09-22 16:01:05 58
en29 Английский zhengqingyuan 2024-09-22 05:40:38 58
en28 Английский zhengqingyuan 2024-09-21 16:31:51 92
en27 Английский zhengqingyuan 2024-09-21 15:59:13 20
en26 Английский zhengqingyuan 2024-09-21 15:57:49 118
en25 Английский zhengqingyuan 2024-09-21 15:50:08 144
en24 Английский zhengqingyuan 2024-09-21 06:36:44 63
en23 Английский zhengqingyuan 2024-09-21 06:07:56 2 Tiny change: 'conclution for naive' -> 'conclutions for naive'
en22 Английский zhengqingyuan 2024-09-20 11:02:07 117
en21 Английский zhengqingyuan 2024-09-20 10:59:30 18
en20 Английский zhengqingyuan 2024-09-20 10:58:55 437
en19 Английский zhengqingyuan 2024-09-20 10:45:05 12 Tiny change: 'er:Timosh]to remind ' -> 'er:Timosh] to remind '
en18 Английский zhengqingyuan 2024-09-20 10:44:52 10 Tiny change: 'ser:Timosh,2024-9-20]to remind' -> 'ser:Timosh]to remind'
en17 Английский zhengqingyuan 2024-09-20 10:44:29 10 Tiny change: 'ser:Timosh]to remind' -> 'ser:Timosh,2024-9-20]to remind'
en16 Английский zhengqingyuan 2024-09-20 10:37:09 29
en15 Английский zhengqingyuan 2024-09-20 10:35:51 2 Tiny change: 'd}(n) <= 68$;\n2. For' -> 'd}(n) <= 64$;\n2. For'
en14 Английский zhengqingyuan 2024-09-20 10:29:16 397
en13 Английский zhengqingyuan 2024-09-20 10:11:11 2 Tiny change: 'on diverse.\n- [user:' -> 'on diverse;\n- [user:'
en12 Английский zhengqingyuan 2024-09-20 10:10:58 394
en11 Английский zhengqingyuan 2024-09-20 08:45:40 20 Tiny change: 'v)$ primes.This can ' -> 'v)$ primes ($2 ^ k$ the worst).This can '
en10 Английский zhengqingyuan 2024-09-20 08:38:08 1 Tiny change: 'e to thanks:\n\n- [us' -> 'e to thank:\n\n- [us'
en9 Английский zhengqingyuan 2024-09-20 08:37:56 887
en8 Английский zhengqingyuan 2024-09-20 08:20:32 23
en7 Английский zhengqingyuan 2024-09-19 11:52:50 5 Tiny change: '{O}(\log_2(v))$ times t' -> '{O}(\log_2 n)$ times t'
en6 Английский zhengqingyuan 2024-09-19 10:15:54 484 (published)
en5 Английский zhengqingyuan 2024-09-19 09:47:36 2 Tiny change: 'or $\operaotrname{O}(\' -> 'or $\operatorname{O}(\'
en4 Английский zhengqingyuan 2024-09-19 09:47:22 20
en3 Английский zhengqingyuan 2024-09-19 09:46:32 17
en2 Английский 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 Английский zhengqingyuan 2024-09-19 09:45:35 1816 Initial revision (saved to drafts)