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 integer

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

example:510D.

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) <= 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
• 990G
• 645F

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.

4.Great common diverse: $$$\operatorname{O}(\log_2 n)$$$ distinct prefix great common diverse

Thanks Ghulam_Junaid 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.

example:475D.

Last:written in the end:

I would like to thank:

• zhengqingyuan who edit the blog;
• AkiLotus,PeruvianCartel for correcting the mistake;
• Ghulam_Junaid to remind me about a feature about great common diverse.