OJ Board

I think 0<=M<=N

Best regards
DM

so how does this solution work for finding the last non-zero digit of n!:

[cpp]#include <stdio.h>
#include <string.h>
#define MAXN 1000

long a[MAXN], l;

void a_div_5(void)
{
int i, plus;

plus = 0;
for (i=0; i<l; i++) {
a = a*2+plus;
plus = a/10;
a = a%10;
}
if (plus>0) a[l++] = plus;
l--;
for (i=0; i<l; i++) a = a[i+1];
}

int main(void)
{
char buffer[MAXN];
long mod[20]={1,1,2,1,4,2,2,4,2,3,4,4,3,4,1,3,3,1,3,2};

int result, n, i, plus, j, one;
FILE *f, *g;

f = stdin;
g = stdout;

while ( fscanf(f, "%s", buffer) != EOF) {
l = strlen(buffer);

for (i=0; i<l; i++) a = buffer[l-1-i] - '0';
one = l==1 && a[0]==1;

result = 1;
while (l>0) {
if (l==1) result = result * mod[a[0]] % 5;
else result = result * mod[a[0] + 10*(a[1]%2) ] % 5;
a_div_5();
}

if (one || result%2==0) fprintf(g, "%d\n", result);
else fprintf(g, "%d\n", result+5);

}
return 0;
}
[/cpp]
a_div_5 is obvious, but what is mod??[cpp][/cpp]

dear Riyad
I dont think your code has any chance for getting accepted

becuase
you want to avoid having 0 by using ,
mult=mult%100000;
which when i> 100000 , for example i=1000000> 20000000 then mult will be 0 and ...
also in your while where x= mult%10, i cant understand why you use a loop, ???

I think the easiest brute force alg is:
S:= 1;
C2:= 0
C5:= 0;
for i:= m+ 1 to n do
j:= i;
while j mod 2= 0 do
j:= j div 2;
Inc (C2);

while j mod 5= 0 do
j:= j div 5;
Inc (C5);
S:= S* (j mod 10);

if C2> C5 then
S:= (S* 2^ (C2- C5) )mod 10
else
S:= (S* 5^ (C5- C2) )mod 10


But I this alg may encounter time limit!
Amir

I solved 10212, but I had some problems with the online judge. If someone supervising the
online judge reads this, then check my submissions numbered 3110597 and 3110602. These
two C programs are essentially the same, except that in one of them I have a "const char *"
having a length 36365 characters (and the online judge says: Wrong Answer), in the other
I broke this string up in a "const char * []", in which every string is of length 220 or less (and
the online judge accepts it). The problem is most likely in the long line, but if I compile these
on my machine, then there is no problem in compiling or running and they give the same answer
for several hundred thousand randomly generated and some special case input. Please,
correct the online judge or the submission method (I do not know which went wrong): I
used the WWW form to submit these programs, and I uploaded the program so there should
not be a copy-paste error in it.

TIA:

Geza

I solved 10212, but I had some problems with the online judge. If someone supervising the
online judge reads this, then check my submissions numbered 3110597 and 3110602. These
two C programs are essentially the same, except that in one of them I have a "const char *"
having a length 36365 characters (and the online judge says: Wrong Answer), in the other
I broke this string up in a "const char * []", in which every string is of length 220 or less (and
the online judge accepts it). The problem is most likely in the long line, but if I compile these
on my machine, then there is no problem in compiling or running and they give the same answer
for several hundred thousand randomly generated and some special case input. Please,
correct the online judge or the submission method (I do not know which went wrong): I
used the WWW form to submit these programs, and I uploaded the program so there should
not be a copy-paste error in it.

TIA:

Geza

Could someone give me a hint ???

I got TLE with my purely force brute algorithm.

Thx in advance...

We must factorize n! into this form: 2^i * 3^j * 5^k * 7^l, and find the corresponding i, j, k, and l.

eg, n=10.
10! = 1.2.3.4.5.6.7.8.9.10 = 2^7.3^4.5^2.7^1
and we also know the lastdigit of 2^k, 3^k, 5^k, and 7^k; 0<=k<=p.

If you still confuse how to factorize it, I will gratefull to tell you more...

Also i amm confused of that...
Scorpion
Please would u be a bit more specific

Sorry~~

Can sombody give me test case ~

thanks~~

65 8
2

5564 665
2

4445 2222
4

7895 2144
2

10 10
8

54 0
0

0 0
0

87 5
4

545454 66666
4

78965 78956
6

You're Wrong. Output for cases n 0 should be 1 instead of 0.

I am getting WA.. I need a lot of inputs and outputs
Can any one help me..
or can any one tell me for which input my program produces wrong output?

thanks

I'm geting WA.
pleeze tell me my code bug.

Integer Overflow

I used "long long" but I got TLE

emotional blind wrote:Integer Overflow

I don't think so.

hamedv, try N=126 M=2. Compute the right answer by hand and compare with your program's output.