zhengqingyuan's blog

By zhengqingyuan, history, 3 months ago, In English

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:

  1. For n104,maxd(n)<=64;
  2. For n5×104,maxd(n)<=100;
  3. For n105,maxd(n)<=128;
  4. For n2×105,maxd(n)<=160;
  5. For n3×105,maxd(n)<=180;
  6. For n5×105,maxd(n)<=200;
  7. For n106,maxd(n)<=240;
  8. For n5×106,maxd(n)<=384;
  9. For n107,maxd(n)<=448;

So if your solution of a problem is O(nmaxd(ai)) or O(d(ai)),it might be correct because for ai107,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 [2n] distinct integers of [ni],1in.

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],1ik 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 [2n] times for distinct numbers.

example:

Last:written in the end:

I would like to thank:

  • Vote: I like it
  • +147
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it +17 Vote: I do not like it

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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :/

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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:

      For references to each of these average order estimates see equations (3) and (18) of the MathWorld reference and Section 22.10-22.11 of Hardy and Wright.

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

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        oh wow, I totally forgot about references lol. I took a look at it, and it makes way more sense now. Thanks!

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Sorry in my country wikipedia is banned and please send here in detail.

»
3 months ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    OK,I'll add it.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what does distinct prefix gcds mean?

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Man, I don't know. Maybe it's just preference, but I don't think "intelliger" is a word.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very interesting. This may be helpful for those who are interested in math.

I also saw a problem involving prefix ORs, which has at most log2(r) different prefixes. Same goes for AND.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

if i am not mistaken, for n104, we have maxd(n)64, not 68.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

+

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I always use the following estimation even though it's incorrect:

The number of divisors of N is O(3N).

It just works very well for N values that we deal with in CP.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +45 Vote: I do not like it

    I use the estimation d(N)=o(nε) because it works very well for the values that I deal with.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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=213052 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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For w(n),ni=1w(n),you should count the distinct prime factors seperately for each of the integers,and add the numbers together.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Congradulations to you and thank you to remind me the problem.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But there's nothing in this post that's helpful in proving the greedy solution for 2013E, or am I missing something?

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I've come out of a solution using conclution 2 and I'll try if it works.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Then what's the point of your comment?

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://cses.fi/problemset/task/1082

Can include this classic problem as well for at most 2*(sqrt(N)) distinct integers (point 5).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for this. Please do more of these if possible!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for the blog!!would be really helpful by more blogs on number theory and math!!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zhengqingyuan (previous revision, new revision, compare).