Блог пользователя TheSleepyDevil

Help In Problem

Автор TheSleepyDevil, история, 7 месяцев назад, По-английски

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 ?

  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится

»
7 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить