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 log2(v) primes (2k 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 w(n),∑ni=1w(n) is O(nloglogn).
example:510D.
2.The number of factors of an integer
First of all,∑ni=1d(n)=∑ni=1[ni]≈nlnn.
Then I've found out that the number of factors of an integer(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:
- For n≤104,maxd(n)<=64;
- For n≤5×104,maxd(n)<=100;
- For n≤105,maxd(n)<=128;
- For n≤2×105,maxd(n)<=160;
- For n≤3×105,maxd(n)<=180;
- For n≤5×105,maxd(n)<=200;
- For n≤106,maxd(n)<=240;
- For n≤5×106,maxd(n)<=384;
- For n≤107,maxd(n)<=448;
So if your solution of a problem is O(nmaxd(ai)) or O(∑d(ai)),it might be correct because for ai≤107,it's sure that d(ai)≤500.
examples:
3.Euler's Function: O(log2n) times to 1.
It's sure that ϕ(n)≤n2 for 2|n,and 2|ϕ(n) for n>1.So if you use operation x=ϕ(x) for x=n initially,it will become 1 in O(log2n) times.
example:
4.Prefixes: O(log2n) distinct prefix great common diverse/and/or
Thanks Ghulam_Junaid and Timosh to remind me about the feature.
For gcd(a1,a2,...,ak),We can add a new integer ak+1 and found:
- If gcd(a1,a2,...,ak)|ak+1,it's sure that gcd(a1,a2,...,ak,ak+1)=gcd(a1,a2,...,ak).
- Otherwise,gcd(a1,a2,...,ak,ak+1)≤[gcd(a1,a2,...,ak)2].
So there are at most log2n distinct prefix great common diverse.
For operator and
or or
,every integers can be written by log2n 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 log2n prefixes and suffixes.
example:
5.At most [2√n] distinct integers of [ni],1≤i≤n.
Known as number theory chunking in public,we can proof that [ni]=[n[ni]],and then split [1,n] to O(√n) sections like [l,r=[nl]],it's really useful while calculating ∑ni=1f([ni]) or it's easy to consider several integer v1,v2,...,vk together when [nvi],1≤i≤k is the same.
If we use Möbius inversion first,we might found that we have to calculate f(xd),using the feature we can found out that we can calculate the function just [2√n] times for distinct numbers.
example:
Last:written in the end:
I would like to thank:
- zhengqingyuan 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
andor
. - AkiLotus to remind me something about prime factors.
- Timosh,The-Winner,GUNNER19_2.0 to provide some examples.
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
Question: why "intelliger" instead of "integer"? Is it an implication that integers are intelligent and sentient beings?
A slight correction on 1: the growth is in fact just O(loglogn) on average.
I think he was talking about the worst case relating to (not necessarily distinct) prime factors, since oftentimes the worst case is of greater importance in competitive programming.
I'm curious about the worst case when we count distinct prime factors though — the wikipedia page you linked says that ω(n)∼lognloglogn when n is a primorial, but I can't see how one would come up with this approximation :/
Ah, I see. I tend to only consider distinct ones (non-distinct can be compressed in map form), so was kinda misreading that part.
For your concern, I looked at the citation which wrote:
Probably the document they meant to mention was
G. H. Hardy and E. M. Wright (2006). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press.
.oh wow, I totally forgot about references lol. I took a look at it, and it makes way more sense now. Thanks!
Sorry in my country wikipedia is banned and please send here in detail.
gcd(x, y) = min(x, y) or gcd(x, y) <= min(x, y) / 2. so we can say there are O(lg(n)) distinct prefix gcds.
OK,I'll add it.
what does distinct prefix gcds mean?
let's say you are computing prefix gcd of an array (similar to prefix sum but you are doing gcd instead of sum), distinct values in this prefix gcd array is "distinct prefix gcds".
Man, I don't know. Maybe it's just preference, but I don't think "intelliger" is a word.
fixed
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
Very interesting. This may be helpful for those who are interested in math.
I also saw a problem involving prefix
OR
s, which has at most log2(r) different prefixes. Same goes forAND
.Thanks.
Could you give me the URL?
1669H - Maximal AND and XOR and OR (from kep.uz)
OK,but I've senn 1669H and found the solution didn't use the feature.
Yeah, there are several ways to solve a problem
OK.
thanks.
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
if i am not mistaken, for n≤104, we have maxd(n)≤64, not 68.
I'll check that.
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
For number 3, another problem example is 1797E - Li Hua and Array, although I am not sure if you could consider it as an application of the trick
OK,I'll add it.
+
I always use the following estimation even though it's incorrect:
The number of divisors of N is O(3√N).
It just works very well for N values that we deal with in CP.
I use the estimation d(N)=o(nε) because it works very well for the values that I deal with.
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
For the number of prefix gcd, it's worth mention that, if we think the values of array as factorized form and map the frequency table of prime factors to a vector(ex. 50=21⋅30⋅52 so we use vector [1,0,2,0,0,0,…] to represent it), then taking gcd of two number is essentially taking element-wise min of their respective vector, and the sum of element in a vector is O(lgn) so we can decrease it O(lgn) times.
You can also think it as an extended result of prefix bitwise and have O(lgn) different value.
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
I don't quite undertand what you are trying to calculate with w(n),∑ni=1w(n) is O(nloglogn)
Let see the case when n=16 then 16log(log16)=16.3165 but the prime factorization of 16 is 2∗2∗2∗2 and clearly has 1 distinct prime factor, and from 1,2,3,4,....16 there are 6 distinct prime factors
EDIT: nvm i didn't realize it was complexity for some reason.
For w(n),∑ni=1w(n),you should count the distinct prime factors seperately for each of the integers,and add the numbers together.
This post made my way back to CM, and 9th place in the last Div. 2, as 2013E - Prefix GCD was literally named "Prefix GCD". I guess I was lucky.
Congradulations to you and thank you to remind me the problem.
But there's nothing in this post that's helpful in proving the greedy solution for 2013E, or am I missing something?
I've come out of a solution using conclution 2 and I'll try if it works.
When doing greedy problems, I usually don't prove my solution. Instead, I try to come up with a counter-test, and if I fail to, I'll assume it works. That's how CP works
Then what's the point of your comment?
In the blog it's written that there are at most log(Amax) different prefix gcds. And when I looked at 2013E, I assumed it has the same idea, as each time it's better to change(decrease) the gcd, which we don't have to do more than log(Amax) times. You can check my code, where I used r=100, where I check best element each time, first is the smallest element, second is the smallest resulting GCD and so on. You don't have to do it more than ~40 times.
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
https://cses.fi/problemset/task/1082
Can include this classic problem as well for at most 2*(sqrt(N)) distinct integers (point 5).
OK
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
Thanks for this. Please do more of these if possible!
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
thanks for the blog!!would be really helpful by more blogs on number theory and math!!
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).
Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).