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 at most $\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 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).↵
↵
# 1.The number of prime factors of an inte
↵
It's sure that the number of prime factors of an inte
↵
example:[510D](https://codeforces.me/problemset/problem/510/D).↵
↵
# 2.The number of factors of an inte
↵
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 inte
↵
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 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).↵
