Some useful conclution for some naive algorithms to solve number theory problem
Разница между en6 и en7, 5 символ(ов) изменены
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](https://codeforces.me/problemset/problem/510/D).↵

# 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:↵

- [1780F](https://codeforces.me/contest/1780/problem/F)↵
- [990G](https://codeforces.me/contest/990/problem/G)↵
- [645F](https://codeforces.me/problemset/problem/645/F)↵


# 3.Euler's Function: $\operatorname{O}(\log_2
(v) 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:[906D](https://codeforces.me/problemset/problem/906/D).↵

История

 
 
 
 
Правки
 
 
  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)