## 11960 - Divisor Game

**Moderator:** Board moderators

### 11960 - Divisor Game

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

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

Some cases, I hope it helps.

Input:
Output:

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

Code: Select all

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

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

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

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)

### 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]

Thats my algorithm.Im getting TLE on this.Please help anyone how to optimize my code?

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]

Thats my algorithm.Im getting TLE on this.Please help anyone how to optimize my code?

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

Imti can u send ur code?

ASU(SUST)

ASU(SUST)

### 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.

### 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.

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

use sqrt(N) for prime factor. I hope u will get Accepted...

ASU(SUST)

### 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.

### 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.

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

here is my NOD funtion
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

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;
}
```

hope you get AC

### 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......

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

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

@plamplam

would u plz share the idea how you decreased ur runtime?I used O(1) outputting and kinda memoization.If u don't have any problem would u plz message me ur mail address...coz,I feel and think discussing and sharing is the best way to learn ... thanks in advance...

would u plz share the idea how you decreased ur runtime?I used O(1) outputting and kinda memoization.If u don't have any problem would u plz message me ur mail address...coz,I feel and think discussing and sharing is the best way to learn ... thanks in advance...