Why if I am trying to precalculate factorials using unsigned long long int there is WA#5?  There are 64 last binary  digits  digits and in this task we are to output at most 32 binary digits.

I got AC with 0.734s:



Who can tell some hints to make it work faster?


Edited by author 08.05.2012 14:47

Edited by author 08.05.2012 14:47

How can i solve this problem with time < 1s?? My result is 1.8 s. Could anybody answer me??

Edited by author 23.10.2008 17:35

Edited by author 23.10.2008 17:35

Calc g() first, you will find g(n)=n. And you can prove it by induction.
Then f(n)=f(n-1)[1+g(n-1)],
you will get f(n)=[1+g(1)][1+g(2)]...[1+g(n-1)].

f(n)=n!

program Ural1528;

var
  p:array[1..10000]of qword;
  q,u,e:array[1..5000]of qword;
  ans:array[1..5000]of qword;
  m:qword;
  a,n,max,x,y:longint;

procedure qsort(l,r:longint);

var
  i,j:longint;
  mid,swap:qword;

begin
  i:=l;j:=r;mid:=u[(i+j)div 2];
  repeat
    while u[i]<mid do inc(i);
    while u[j]>mid do dec(j);
    if i<=j then
    begin
      swap:=u[i];u[i]:=u[j];u[j]:=swap;
      swap:=q[i];q[i]:=q[j];q[j]:=swap;
      swap:=e[i];e[i]:=e[j];e[j]:=swap;
      inc(i);dec(j);
    end;
  until i>j;
  if i<r then qsort(i,r);
  if l<j then qsort(l,j);
end;

procedure readdata;

begin
  n:=0;max:=0;
  repeat
    readln(x,y);
    if (x=0)and(y=0) then exit;
    inc(n);inc(max);
    if x>=y then begin
      ans[n]:=0;
      dec(max);
    end else begin
      q[max]:=x;u[max]:=y;e[max]:=n;
    end;
  until (x=0)and(y=0);
end;

function gcd(o,z:qword):qword;

begin
  if z=0 then exit(o)
  else exit(gcd(z,o-o div z*z));
end;

procedure main;

var
  i,j,mu:longint;
  o:qword;

begin
  i:=1;
  j:=1;
  while i<=max do
    begin
      m:=1;
      mu:=0;
      o:=1;
      while (i<=max)and(trunc(ln(m)/ln(10))+trunc(ln(u[i])/ln(10))-trunc(ln(o)/ln(10))<=18)do
        begin
          m:=m div o;
          m:=m*u[i];
          if mu<q[i] then mu:=q[i];
          inc(i);
          if i<=max then
          if u[i]>m then o:=gcd(u[i],m)
          else o:=gcd(m,u[i]);
        end;
      p[1]:=1;
      for a:=2 to mu do
        p[a]:=p[a-1]*a mod m;
      for a:=j to i-1 do
        ans[e[a]]:=p[q[a]]mod u[a];
      j:=i;
    end;
end;

procedure writedata;

begin
  for a:=1 to n do
    writeln(ans[a]);
end;

begin
  readdata;
  qsort(1,max);
  main;
  writedata;
end.

Why WA5?
I already get AC.But I want to make it faster, so Where is wrong?

[code deleted]

Edited by moderator 04.02.2020 18:17

Can anyone tell me or give me a link as to how the answer to the question is n!%p

I got TLE#11 when i submitted the following code
[code deleted]

Edited by author 11.02.2008 15:27

Edited by moderator 04.02.2020 18:20

I hate long numbers!!!
I am begginer and I don't know them. so I have big problems.
I wrote an algorithm but it doesn't work because f is very big!!!


----------------------------------------
I've made it!!!
whithout long arithmetics

Edited by author 18.02.2007 16:25

[code deleted]

Edited by moderator 04.02.2020 18:22

Can anyone enlighten me what causes this OLE ?

I thought my code was harmless, and I am calculating n!%p. At least that's what I am trying to do.


#include<stdio.h>

int main(){

    long long f,g,n,p;
    scanf("%lld %lld",&n,&p);
    while(n+p != 0){
        [code deleted]
        printf("%lld\n",f);
        scanf("%lld %lld",&n,&p);
    }
    return 0;

}

Edited by moderator 04.02.2020 18:32

As you can see, actual number of testcases in this problem is much less than 10000. Many of you will get TL in the tests with 10000 testcases. New tests will be added soon and maybe TL for this problem will be increased. Write more effective solutions. :)

I got WA #5, who can explain me why???
thnks a lot :)

pleas give some examples else than in the problem
maybe
10 100000
9 1000000

Edited by author 18.02.2007 15:03