## 11960 - Divisor Game

Moderator: Board moderators

regan
New poster
Posts: 4
Joined: Wed Apr 28, 2010 6:24 pm

### 11960 - Divisor Game

Can any one help me by providing some more cases ....

lgarcia
New poster
Posts: 16
Joined: Mon Sep 14, 2009 7:49 pm
Location: Venezuela

### Re: 11960 Divisor Game Getting WA!!

Some cases, I hope it helps.

Input:

Code: Select all

``````20
1
10
100
1000
10000
100000
1000000
2
3
4
5
6
7
8
50
534534
32423
12354
8980
2332``````
Output:

Code: Select all

``````1
10
96
840
9240
98280
997920
2
3
4
4
6
6
8
48
498960
30240
10080
7560
2160``````

iriz7482
New poster
Posts: 15
Joined: Mon Apr 04, 2011 3:18 pm

### Re: 11960 Divisor Game Getting WA!!

This problem is pretty similar to problem 294 - Divisors. I tried to find NOD (number of divisors) of all number in a certain range or precaculate NOD of all number from 1 to 1000000 but got TLE. Is there any better method to solve this problem? Please help

robot
New poster
Posts: 29
Joined: Sun May 24, 2009 8:39 pm

### Re: 11960 Divisor Game Getting WA!!

Actually the problem is a simple precalculating problem...
1. First of all u generate the divisor number using seieve div(n)= n1^(p1+1) * n2^(p2+1)......)
2. next u precalculate maxdiv 1 to range
suppose div[] is a calculating of number of divisor
mdiv[1]=1;
mind[1]=1;
if div[2] >=mdiv[1] {
mdiv[2]=div[2];
mind[2]=2;}
else {
mdiv[2]=mdiv[2-1]
mind[2]=mind[2-1];
}

finally just print mind[n];
ASU(SUST)

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Contact:

### Re: 11960 Divisor Game Getting WA!!

Hello,Im getting TLE in this problem.I precalculated result for every number from 1 to 1e6 and outputted in O(1) time.My working procedure is like:
1)Generate all prime number upto sqrt(1e6) using sieve
2)factorize each number from 1 to 1e6.Then I used the formula for a number n=p1^n*p2^m ,NOD(number_of_divisor)=(n+1)*(m+1)
3)on getting the NOD,compare it with previous one's NOD.If (current NOD>=previous NOD) then TBO(to_be_outputted)[current_num]=current_num else
TBO[current_num]=TBO[current_num-1]

robot
New poster
Posts: 29
Joined: Sun May 24, 2009 8:39 pm

### Re: 11960 Divisor Game Getting WA!!

Imti can u send ur code?
ASU(SUST)

iriz7482
New poster
Posts: 15
Joined: Mon Apr 04, 2011 3:18 pm

### Re: 11960 Divisor Game Getting WA!!

hey Imti your algo is the same as mine. I remember it took nearly 2 seconds to precaculate all NOD of all number from 1 to 1e6, so you may not have enough time to output your result
Last edited by iriz7482 on Sun May 01, 2011 1:29 pm, edited 1 time in total.

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Contact:

### Re: 11960 Divisor Game Getting WA!!

This is my code.I just couldn't recall any better idea right now to solve the problem..

Code: Select all

``````//Code Removed After getting Accepted
'
``````
Last edited by Imti on Sun May 01, 2011 4:56 pm, edited 1 time in total.

robot
New poster
Posts: 29
Joined: Sun May 24, 2009 8:39 pm

### Re: 11960 Divisor Game Getting WA!!

Imti ur code is right, but ur fac() funtion has too much complexity. so change this method. and try prime factor efficiently.
use sqrt(N) for prime factor. I hope u will get Accepted...
ASU(SUST)

iriz7482
New poster
Posts: 15
Joined: Mon Apr 04, 2011 3:18 pm

### Re: 11960 Divisor Game Getting WA!!

after viewing Imti's code I fixed my output from O(n/2) to O(1) and got AC in 1.7 secs . Now I'm thinking another algo to decrease my running time .
Last edited by iriz7482 on Sun May 01, 2011 4:32 pm, edited 1 time in total.

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Contact:

### Re: 11960 Divisor Game Getting WA!!

Thanks robot and iriz... for ur reply..I actually tried several method instead of my "fac()" function..but still getting TLE..would u(robot or iriz)please tell me more clearly about how can I improve my fac() function...
Last edited by Imti on Sun May 01, 2011 4:51 pm, edited 3 times in total.

iriz7482
New poster
Posts: 15
Joined: Mon Apr 04, 2011 3:18 pm

### Re: 11960 Divisor Game Getting WA!!

here is my NOD funtion

Code: Select all

``````long NOD(long n, long a[])
{
long r=1, i=0, j;
while(n>1)
{
if(isprime(n)) //if n is a prime number
{
r*=2;
break;
}
while(n%a[i]!=0)
i++;
j=0;
while(n%a[i]==0)
{
n/=a[i];
j++;
}
r*=(j+1);
}
return r;
}``````
I store prime numbers from 2 to sqrt(n) in the array a[]. a[0]=2, a[1]=3, a[3]=5,....
hope you get AC

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Contact:

### Re: 11960 Divisor Game Getting WA!!

Now,I got Accepted it with runtime of 0.364s.. ..I actually didn't change my fac() function..rather I used some already computed value there in fac() function which has reduced run time dramatically... ...Thanks robot and iriz72......

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 11960 Divisor Game Getting WA!!

Nice problem! It took me a while though to figure out how to output the result quickly. I got AC in 0.676 seconds although I later decreased my runtime to 0.020
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm