11960 - Divisor Game

[regan]

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

[lgarcia]

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]

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]

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]

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?

[robot]

Imti can u send ur code?
ASU(SUST)

[iriz7482]

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

[Imti]

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
'

[robot]

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]

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 .

[Imti]

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

[iriz7482]

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]

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]

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

[Imti]

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