Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

DMGR's blog

Solve number theory Inclusion/Exclusion problems without using exponential time
By DMGR, history, 9 years ago, In English

For some number theory problems like finding Euler Totient Function for some number N,the method involves multiplying N by (1-1/p) for all primes p which divide N. This takes care of Inclusion Exclusion step as all additions/subtractions correspond to Inclusion/Exclusion step. However if the problem is modified to finding all numbers below K which are coprime to N, we cannot directly carry on the multiplications as some of the primes may not divide K completely and instead of this we have to carry on Integer divisions corresponding to each combination of prime divisors of N(2^x,if x prime divisors). So the solution which was linear in number of prime divisors is rendered exponential. Is their someway around this complication.

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think Euler totient function is still exponential in terms of divisors ,

For example , if you run the Erathostenes Sieve version OR if you run the backtracking for all prime divisors of X for every 1<=X<=N you will do the same number of steps

The complexity quickness on Erathostenes Sieve comes from the fact that you can find the prime divisors very fast , instead of doing SQRT(X) steps for a random digit number.

I may be wrong as i just woke up from sleep :) , please correct me then :D

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Edit : What i meant is that i you sum UP the total number of steps

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Oh i understood it bad , as usual , You cannot solve normal inclusion/Exclusion problems without using expenential time in terms of divisors or something.

Euler totient function is a particular special case because it holds the property :

For every a,b two integers with gcd(a,b)!=1 φ(A⋅B)=φ(A)⋅φ(B) From this thing you can derive a nice mathematical formula instead of doing inclusion/exclusion

But for a general case you need some kind of back-tracking

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks. I was under the impression that there might be some shortcut technique which might give the answer even in this case but I think I was wrong.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What do you want to do? E.g. you can solve the problem "count all numbers below K which are coprime to N" with this approach (russian only) in time, where x is a number of prime divisors on N, if you know all prime divisors of N.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I was unable to understand the blog in the link as google translation was really unfathomable. The problem I was trying to solve was this. I was thinking of finding all the coprime fractions for all denominator values less than or equal to N which fall less than x/y. But I was exceeding the given time limit by 10 times. I thought that I might better it by finding someway to calculate the coprime fractions in linear time of number of prime divisors but I think I was wrong. I will try finding some other way. Thanks.

    → Reply