TheSleepyDevil's blog

Help In Problem

By TheSleepyDevil, history, 3 years ago, In English

You Have Number N initialy equal to 1 , and there is 2 operations : 1) 1 x : multiple n by , n=n*x 2) 2 x : check if n%(x!)=0 , n mod (factorial x) = 0

Query up to 1e5 , x up to 1e6

Any hint ?

  • Vote: I like it
  • -11
  • Vote: I do not like it

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

You can get all the primes till 1e6 using seive then you can set a variable M=1 which tells the maximum value of M for which n is divisible by M!, for a query of type 1 x add the prime factorization of x in the residual product array which stores the powers of primes at the indexes now run a while loop checking if product array is divisible by M+1 if so, increment M by 1 and remove the prime factorization from the array. For query of type 2 x simply give yes if M>=x else no. Expected time complexity O((Q)log(1e6))

→ Reply