You are not logged in. Please login at www.codechef.com to post your questions!

×

TLE in DEMENTIA14 MULFACT

I have submitted the solution for the problem MULFACT but it got TLE.Here's my code :

#include<`bits/stdc++.h`>
using namespace std;
#define MOD 329885391853
#define LL unsigned long long

LL N,i,P,F;
long T;

LL mulMod(LL A,LL B)
{
    LL R=0LL;

    while(A!=0)
    {
        if(A&1)
        R=(R+B)%MOD;

        A>>=1;
        B=(B<<1)%MOD;
    }

    return R;
}

LL Fact[999945]={1LL};

LL Pro[999945]={1LL};

void precalc()

{

    Fact[1]=1LL;

    Pro[1]=1LL;

    for(i=2LL;i<=999982LL;i++)
    {
        Fact[i]=(Fact[i-1]*i)%MOD;

        Pro[i]=mulMod(Pro[i-1],Fact[i]);
    }
}

int main() 
{
    precalc();

    scanf("%ld",&T);

    while(T--)
    {

        F=1LL,P=1LL;
        scanf("%llu",&N);
        if(N>=999983)
        printf("0\n");
        else

{

printf("%llu\n",Pro[N]);

}


}

return 0;

}

Is there any way to optimise it?

asked 06 Mar '14, 01:05

knb_dtu's gravatar image

2★knb_dtu
410620
accept rate: 22%

edited 06 Mar '14, 01:43

bit_cracker007's gravatar image

3★bit_cracker007
5.7k266868


Also u can modify you multMod function .. complexity of the mulmod function can be reduced .. have a look at this solution for more information... http://www.codechef.com/viewsolution/3501807

link

answered 06 Mar '14, 11:01

rednivrug15's gravatar image

5★rednivrug15
13125
accept rate: 0%

@knb_dtu yes same thing happened with me as well,solution gave TLE in C++ 4.3.2 and AC in C++ 4.8.1.

link

answered 06 Mar '14, 01:33

chandan11111's gravatar image

3★chandan11111
3.6k133555
accept rate: 10%

edited 06 Mar '14, 01:42

same thing happened to me but i guess it would have bee wiser to store the factorials and the fact(m) value till 999983..many people did it that way

link

answered 06 Mar '14, 09:43

Sandeepripping's gravatar image

4★Sandeepripping
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×234
×105

question asked: 06 Mar '14, 01:05

question was seen: 932 times

last updated: 06 Mar '14, 11:01