Divisors of a Number

#1

Is there any faster algo to find all divisors of a number other than this
https://ide.codingblocks.com/s/55692.
If not then how to prevent TLE in
ques: https://hack.codingblocks.com/contests/c/547/1157
code: https://ide.geeksforgeeks.org/O0Vc3yAz0Z

#3

if you are finding all the divisors then Required complexity O(sqrt(n))
If you are finding only the prime divisors than use min Sieve.

#4

then the TLE ?, similar to what we got in its easier version :slight_smile:

#5

I will debug this code tonight

#6

its the same code btw, just replaced the O(1) statements to a loop as m is different for each pile in the winner function

#7

you can precompute the divisors of every number.
Check if it is working or not.
Precompute like Sieve.

#8

Try this blog

https://codeforces.com/blog/entry/53106
and use DP to store Grundy of All number as precomputed values
I think it will work

#9

precomputing divisors is giving abort signal for numbers greater than 330001 in both seive and root(n) approaches.
code: https://ide.codingblocks.com/s/55706

#10

chrome
chrome1280×720 59.4 KB

Try this one.

#11

It will cross 5 sec limit in mid run. It isn’t optimied at all

#12

the code I wrote reaches 320001 in just 1.8 secs but gets aborted for higher numbers

#13

https://ide.codingblocks.com/s/55720
this one also gives TLE

#14

let me write my code and I will share the link of my code

#15

Refer this code:
https://ide.codingblocks.com/s/55743

#16

you are getting TLE as you are not using DP to store values

1 Like
#17

k thanks. Too bad I don’t like using DP :sweat_smile: