Here are some useful conclution for bruteforce to solve number theory problem,I hope you can know something about it and solve number theory problems more easilynaive 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://mirror.codeforces.com/problemset/problem/510/D).↵
↵
#12.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://mirror.codeforces.com/contest/1780/problem/F)↵
- [990G](https://mirror.codeforces.com/contest/990/problem/G)↵
- [645F](https://mirror.codeforces.com/problemset/problem/645/F)↵
↵
↵
#23.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](https://mirror.codeforces.com/problemset/problem/906/D).↵
↵
# 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://mirror.codeforces.com/problemset/problem/510/D).↵
↵
#
↵
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://mirror.codeforces.com/contest/1780/problem/F)↵
- [990G](https://mirror.codeforces.com/contest/990/problem/G)↵
- [645F](https://mirror.codeforces.com/problemset/problem/645/F)↵
↵
↵
#
↵
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://mirror.codeforces.com/problemset/problem/906/D).↵
