AMnu's blog

By AMnu, 4 months ago, In English,

Understanding Number Theory Problems

Some people regard number theory is little bit difficult. However, it's actually an easy topic. Most of people only dare to solve kinds of problems that has simple complexity (like O(N), O(NlogN), O(N^2), etc) such as DP, greedy, and bruteforce. Here, we will talk about how to calculate or estimate the complexity of number theory problems.

As you see in some problemsets, number theory problem usually placed in the hardest problem. For example :

  1. problem 912, placed in E (hardest)

  2. problem 915, placed in G (hardest)

  3. problem 919, placed in E (second hardest)

  4. problem 920, placed in F and G (first and second hardest)

  5. problem 922, placed in F (hardest)

Let's start our discussion.

Estimate the Complexity and Problem Example

In most of number theory problems, sometimes calculate one by one is prefer than calculate all in one. Let me explain using some examples.

1, 907F — Power Tower

For a problem with range query, we usually need to compute that range at once. In that problem, may be somebody thinks that it using prefix or segment tree to calculate the answer faster. But, who thinks that we have to compute them one by one. How it can be, O(N^2) must be TLE? But in fact, it will be faster than you imagine. If we calculate the modulo of it, { (a^b) mod m = a^(b mod phi(m)) mod m }, { (a^b^c) mod m = a^b^(c mod phi(phi(m))) mod m }, and so on. phi(x) is the number of natural number y < x such that gcd(x,y) = 1. It's known that x > phi(x). So, phi(phi(...phi(x))) will be equal to 1. When that value reaches 1, we know that any number mod 1 is equal to 0. Then, we can directly know that the rest power in modulo is equal to 0 and no need to calculate the rest. But, in this problem, in case when the result is equal to 0, we should return the minimum between the pointed number and 2 instead of 0. Because, any number to the power of 0 is equal to 1 and the actual number isn't equal to 1. The question is, how many phi needed to reaches 1? For x not greater than a billion, 30 times is enough.->O(logN) And the total query complexity is O(30N).

2, 920F — SUM and REPLACE

Once again, some people thinks that we need to replace a range in query at once. How to replace a range of number with the number of its positive divisor at once? Using segment tree lazy propagation? Of course not. Actually, we just need to replace them one by one. Why? Because, for x less than or equal to 2, the number of positive divisor is equal to x itself. So, we need to replace all x greater than 2 only. Then, how many replacement needed to make x reaches to 2 or less? Is it 1000?->O(sqrtN) Is it 20?->O(logN) Actually, for x not greater than a million, we need no more than 6 replacements only. O(6N) that's enough.

3, You may request more number theory problems in comment below.

Collected Data in Complexity Table

1, number of relative prime number less than x will reach 1 in :

- no more than 10, for x less than 1000

- no more than 20, for x less than 10^6

- no more than 30, for x less than 10^9

2, number of positive divisor will reach 2 in :

- no more than 3, for x less than 10

- no more than 5, for x less than 1000

- no more than 6, for x less than 10^6

- no more than 7, for x less than 10^9

3, number of different prime divisor of x :

- no more than 4, for x less than 300 < 10^3

- no more than 5, for x less than 3000

- no more than 6, for x less than 30000 < 10^6

- no more than 7, for x less than 6x10^6

- no more than 8, for x less than 10^7

- no more than 9, for x less than 3x10^8 < 10^9

- no more than 10, for x less than 7x10^9

- no more than 15, for x less than 7x10^17 < 10^18

4, sieve of Erastosthenes complexity with optimation :

- 1,4x10^3 for 1000

- 2,1x10^6 for 10^6

- 2,2x10^7 for 10^7

- 2,4x10^8 for 10^8

Challenge

I wonder about total positive divisor of x that less than x. What if in problem 920F, the function D(x) changed into total positive divisor of x that less than x. There will be some cycle.

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

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

explain 912E. please.

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

    First of all, assume that the worst case is when the number of integer such that all its prime divisors are in that set is maximum. It happens when the input is first 16 prime numbers :

    16

    2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53

    We need to find all those number less than 10^18 only. Actually, we can divide that prime numbers into two part. Lets see which one is the most optimal.

    - If we divide into first 3 and last 13, the number of integer that fulfill the condition is 10917 in the first part and 9480065 in the second part.
    
    - If we divide into first 4 and last 12, the number of integer that fulfill the condition is 66061 in the first part and 3308885 in the second part.
    
    - If we divide into first 5 and last 11, the number of integer that fulfill the condition is 276997 in the first part and 1294866 in the second part.
    
    - If we divide into first 6 and last 10, the number of integer that fulfill the condition is 958460 in the first part and 505756 in the second part.
    
    - If we divide into first 7 and last 9, the number of integer that fulfill the condition is 2750000 in the first part and 201456 in the second part.
    
    - If we divide into first 8 and last 8, the number of integer that fulfill the condition is 7039193 in the first part and 78138 in the second part.
    
    - If we divide into first 9 and last 7, the number of integer that fulfill the condition is 16038303 in the first part and 30121 in the second part.

    The best partition is first 6 and last 10. But, you can choose another one. We can bruteforce them to find all fulfilled number. Here I just explain the number theory part, I left the remaining part for your exercise. I believe you understand the remaining part using binary search.

    That's really a nice problem. Thank you.

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

Here is a statistic table concerning about divisors. Hope it will be helpful to you.

Note:

Define that , which represent the number of distinct prime divisors of n, the number of prime divisors of n and the number of divisors of n respectively.

Obviously, and . In addition, with the fix at finite values, we have .

Also, define that .

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

Number theory is an easy problem if you know the idea behind it. What makes it hard is how to get such idea. Any advices how to get the idea to solve the problem in less than 1 hour? Thank you.

Nice blog btw.