|
|
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 You should minimize the number of mod operations. for example when I use mod each iteration i got 0.9 sec. But when I minimized the number of mod operations I got 0.56 sec. You should use long f(java) and calculate (f mod p) when f > 10^14, but not each time you calculate your f. How can i solve this problem with time < 1s?? My result is 1.8 s. Could anybody answer me?? The same question. I got AC in 1.7 sec, how to make it faster? Edited by author 01.07.2008 18:46 You should minimize the number of mod operations. for example when I use mod each iteration i got 0.9 sec. But when I minimized the number of mod operations I got 0.56 sec. You should use long f(java) and calculate (f mod p) when f > 10^14, but not each time you calculate your f. Edited by author 23.10.2008 17:35 Edited by author 23.10.2008 17:35 I accepted in 0.75 sec and 188 KB in C++ 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 Use 64-bit type, like long long or __int64 (maybe with prefix unsigned) Edited by author 19.02.2007 13:49 Can someone give test examples, please? Edited by author 05.10.2007 13:17 I think that you're the DUNKEY!!!!!!!!!!!!! use __int64 instead of int 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 alforithm corect for that problem is not using strings :D My program takes only 15 lines :D My AC Program only takes 13 lines. There's no need to use "LONG" numbers Just this: [code deleted] Edited by moderator 04.02.2020 18:21 But what about p? And don't you have to use int64 type instead of longint? is this test true? if yes then why i have WA2????? 10000 1999999999 0 0 1854601288 [code deleted] Edited by moderator 04.02.2020 18:22 Well, numbers can become more than p. Try to use int64. But I can't say exactly. Edited by author 07.11.2007 23:42 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. :) Limitations were changed. Now all tests contain 5000 testcases or less. Timelimit was increased from 2 to 3 sec. You can see that correct Java solution can pass TL easily. By the way some new tests were added. 70 authors got TL and Crash. By the way, new tests still too weak... Solution, that works about 5 secs. on my tests (within limitations), passes all timus tests within 1.6 secs. I think, number of tetscases should be decreased down to 1000, and timelimit should be decreased to 2 secs... You can mail me your tests: sandro sobaka plotinka ru . I got WA #5, who can explain me why??? thnks a lot :) -11 mod 10 = ? (-1 or 9) in this problem? pleas give some examples else than in the problem maybe 10 100000 9 1000000 Edited by author 18.02.2007 15:03 |
|
|