AMnu's blog

By AMnu, history, 3 months ago, In English,

I wonder, what is the percentage of ioi 2019 contestant that attempt problem line without any randomization?

Read more »

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

By AMnu, 16 months ago, In English,

What is the largest number less than 2^64 which has exactly 90 positive divisors ?

Read more »

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

By AMnu, 21 month(s) 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.

Read more »

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