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 AkiLotus 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.

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,\operatorname{d}(n) <= 64$$$;
2. For $$$n \le 5 \times 10 ^ 4,\operatorname{d}(n) <= 100$$$;
3. For $$$n \le 10 ^ 5,\operatorname{d}(n) <= 128$$$;
4. For $$$n \le 2 \times 10 ^ 5,\operatorname{d}(n) <= 160$$$;
5. For $$$n \le 3 \times 10 ^ 5,\operatorname{d}(n) <= 180$$$;
6. For $$$n \le 5 \times 10 ^ 5,\operatorname{d}(n) <= 200$$$;
7. For $$$n \le 10 ^ 6,\operatorname{d}(n) <= 240$$$;
8. For $$$n \le 5 \times 10 ^ 6,\operatorname{d}(n) <= 384$$$;
9. For $$$n \le 10 ^ 7,\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.

In fact,it can be related to problems about power,when we try to solve the problem using Euler's Theorem or Extend Euler's Theorem.

example:

• 906D
• 1797E

4.Prefixes: $$$\operatorname{O}(\log_2 n)$$$ distinct prefix great common diverse/and/or

Thanks Ghulam_Junaid and Timosh 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
• 1139D
• 2005D
• 2013E

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 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
• 1082 in CSES
• P1829 in Luogu
• P3327 in Luogu

Last:written in the end:

I would like to thank:

• OtterZ who edit the blog;
• AkiLotus,PeruvianCartel,peltorator for correcting the mistake;
• Ghulam_Junaid to remind me about a feature about great common diverse;
• Timosh to remind me about a feature about operator and and or.
• AkiLotus to remind me something about prime factors.
• Timosh,The-Winner,swarup19 to provide some examples.