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 $\log_2(v)$ primes ($2 ^ k$ the worst).This can be used for bruteforce and State compression.↵
↵
Thanks [user:AkiLotus,2024-09-21] to remind me that for the number of distinct prime factors of a integer $\operatorname{w}(n)$,$\sum_{i = 1}^n \operatorname{w}(n)$ is $\operatorname{O}(n \log \log n)$.↵
↵
example:[510D](https://codeforces.me/problemset/problem/510/D).↵
↵
# 2.The number of factors of an integer↵
↵
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 integer($\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) <= 64$;↵
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)↵
- [1797E](https://codeforces.me/contest/1797/problem/E)↵
↵
# 4.Prefixes: $\operatorname{O}(\log_2 n)$ distinct prefix great common diverse/and/or↵
↵
Thanks [user:Ghulam_Junaid,2024-09-21] and [user:Timosh,2024-09-21] 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:↵
↵
- [475D](https://codeforces.me/problemset/problem/475/D)↵
- [1139D](https://codeforces.me/contest/1139/problem/D)↵
- [2013E](https://codeforces.me/contest/2013/problem/E)↵
↵
# 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.↵
↵
If we use [Möbius inversion](https://codeforces.me/blog/entry/53925) first,we might found that we have to calculate $\operatorname{f}(\frac{x}{d})$,using the feature we can found out that we can calculate the function just $[2\sqrt{n}]$ times for distinct numbers. ↵
↵
example:↵
↵
- [ARC060B in AtCoder](https://atcoder.jp/contests/abc044/tasks/arc060_b)↵
- [1082 in CSES](https://cses.fi/problemset/task/1082)↵
- [P1829 in Luogu](https://www.luogu.com.cn/problem/P1829)↵
- [P3327 in Luogu](https://www.luogu.com.cn/problem/P3327)↵
↵
# Last:written in the end:↵
↵
I would like to thank:↵
↵
- [user:zhengqingyuan,2024-09-21] who edit the blog;↵
- [user:AkiLotus,2024-09-21],[user:PeruvianCartel,2024-09-21],[user:peltorator,2024-09-21] for correcting the mistake;↵
- [user:Ghulam_Junaid,2024-09-21] to remind me about a feature about great common diverse;↵
- [user:Timosh,2024-09-21] to remind me about a feature about operator `and` and `or`.↵
- [user:AkiLotus,2024-09-21] to remind me something about prime factors.↵
- [user:Timosh,2024-09-21],[user:The-Winner,2024-09-21],[user:GUNNER19_2.0,2024-09-21] to provide some examples.
↵
# 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 $\log_2(v)$ primes ($2 ^ k$ the worst).This can be used for bruteforce and State compression.↵
↵
Thanks [user:AkiLotus,2024-09-21] to remind me that for the number of distinct prime factors of a integer $\operatorname{w}(n)$,$\sum_{i = 1}^n \operatorname{w}(n)$ is $\operatorname{O}(n \log \log n)$.↵
↵
example:[510D](https://codeforces.me/problemset/problem/510/D).↵
↵
# 2.The number of factors of an integer↵
↵
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 integer($\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) <= 64$;↵
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)↵
- [1797E](https://codeforces.me/contest/1797/problem/E)↵
↵
# 4.Prefixes: $\operatorname{O}(\log_2 n)$ distinct prefix great common diverse/and/or↵
↵
Thanks [user:Ghulam_Junaid,2024-09-21] and [user:Timosh,2024-09-21] 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:↵
↵
- [475D](https://codeforces.me/problemset/problem/475/D)↵
- [1139D](https://codeforces.me/contest/1139/problem/D)↵
- [2013E](https://codeforces.me/contest/2013/problem/E)↵
↵
# 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.↵
↵
If we use [Möbius inversion](https://codeforces.me/blog/entry/53925) first,we might found that we have to calculate $\operatorname{f}(\frac{x}{d})$,using the feature we can found out that we can calculate the function just $[2\sqrt{n}]$ times for distinct numbers. ↵
↵
example:↵
↵
- [ARC060B in AtCoder](https://atcoder.jp/contests/abc044/tasks/arc060_b)↵
- [1082 in CSES](https://cses.fi/problemset/task/1082)↵
- [P1829 in Luogu](https://www.luogu.com.cn/problem/P1829)↵
- [P3327 in Luogu](https://www.luogu.com.cn/problem/P3327)↵
↵
# Last:written in the end:↵
↵
I would like to thank:↵
↵
- [user:zhengqingyuan,2024-09-21] who edit the blog;↵
- [user:AkiLotus,2024-09-21],[user:PeruvianCartel,2024-09-21],[user:peltorator,2024-09-21] for correcting the mistake;↵
- [user:Ghulam_Junaid,2024-09-21] to remind me about a feature about great common diverse;↵
- [user:Timosh,2024-09-21] to remind me about a feature about operator `and` and `or`.↵
- [user:AkiLotus,2024-09-21] to remind me something about prime factors.↵
- [user:Timosh,2024-09-21],[user:The-Winner,2024-09-21],[user:GUNNER19_2.0,2024-09-21] to provide some examples.
