10212 - The Last Non-zero Digit.

[Dominik Michniewski]

I think 0<=M<=N

Best regards
DM

[bugzpodder]

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]

[Amir Aavani]

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

[G]

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

[G]

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

[Antonio Ocampo]

Could someone give me a hint ???

I got TLE with my purely force brute algorithm.

Thx in advance...

[I LIKE GN]

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

[ckm111]

Sorry~~

Can sombody give me test case ~

thanks~~

[Wei-Ming Chen]

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

[JaviGS]

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

[emotional blind]

I am getting WA.. I need a lot of inputs and outputs
Can any one help me..

Code: Select all

CODE removed after getting accepted

or can any one tell me for which input my program produces wrong output?

thanks

[hamedv]

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

Code: Select all

#include <stdio.h>

int n, m, i, a, x;

int main()
{
	while (scanf("%d%d", &n, &m) != EOF)
	{
		a = 1;
		for (i = n-m+1; i <= n; i++)
		{
			a *= i;
			while (a % 10 == 0) a /= 10;
			a %= 10;
		}
		printf("%d\n", a);
	}
}

[emotional blind]

Integer Overflow

[hamedv]

I used "long long" but I got TLE

[mf]

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.