10212  The Last Nonzero Digit.
Moderator: Board moderators

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan
Well, I think you can make it a bit faster if you will calculate the last digit not in function but in code (just %10  why to put it into a special function?). Then you may use !(tp&1) instead of !(tp%2) and similarly tp>>=1 instead of tp/=2, as I don't know if the compiler can replace this operations itself.
And another thing: count2 is always >= count5.
Good luck.
Andrey.
And another thing: count2 is always >= count5.
Good luck.
Andrey.

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan
Oh, I'm really confused about count2 and 5
You see I forgot that we count the last digit of nPm  I thought we count the last digit of factorial and really if we would deal with factorials then count2>=count5. My program even gives the wrong answer on your test, but AC on Valladolid. Of course I was wrong but the judges are also wrong... So it means there is no such test. But perhaps soon my program will get WA on rejudgement.
About !(tp&1) I want to say that when we want to check if a number is even or odd we needn't use %2 operation. We may use bitwise AND operation to get the least significant bit of a number and if this bit is zero then the number is even, otherwise it is odd. So construction !(x&1) gives true (or 1) only when x is even.
And operation of binary shift may be used to divide a number by 2.
x>>1 is equal to x/2 if x is integer.
x>>2 is equal to x/4 if x is integer.
and so on.
Well... sorry for counts and get AC on the problem.
Andrey.
You see I forgot that we count the last digit of nPm  I thought we count the last digit of factorial and really if we would deal with factorials then count2>=count5. My program even gives the wrong answer on your test, but AC on Valladolid. Of course I was wrong but the judges are also wrong... So it means there is no such test. But perhaps soon my program will get WA on rejudgement.
About !(tp&1) I want to say that when we want to check if a number is even or odd we needn't use %2 operation. We may use bitwise AND operation to get the least significant bit of a number and if this bit is zero then the number is even, otherwise it is odd. So construction !(x&1) gives true (or 1) only when x is even.
And operation of binary shift may be used to divide a number by 2.
x>>1 is equal to x/2 if x is integer.
x>>2 is equal to x/4 if x is integer.
and so on.
Well... sorry for counts and get AC on the problem.
Andrey.

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
P 10212
Well, I have try your advise by count %2 my !(tp&1), butt I still get TLE.
How about count /= 5 , are you have the solution ?
Thanks.
How about count /= 5 , are you have the solution ?
Thanks.

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
P 10212
Well, I have try your advise by count %2 my !(tp&1), butt I still get TLE.
How about count /= 5 , are you have the better solution ?
Thanks.
How about count /= 5 , are you have the better solution ?
Thanks.

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
Andrey, I got it in less then 1 sec.
As we know n! = 2^i * 3^j * 5^k * 7^l
I get the power of 2 by:
i = n div 2 + (n div 2) div 2 + ((n div 2) div 2) div 2
+ ... (until n div 2 div 2 div 2... = 0);
similiar for j, we can get it from div 5.
(We don't need to do iteration from nm+1 to n).
I suggest you read the site:
Http://ipsc.ksp.sk/problems/ipsc1999/sol_d.php
Bye,
RED SCORPION
As we know n! = 2^i * 3^j * 5^k * 7^l
I get the power of 2 by:
i = n div 2 + (n div 2) div 2 + ((n div 2) div 2) div 2
+ ... (until n div 2 div 2 div 2... = 0);
similiar for j, we can get it from div 5.
(We don't need to do iteration from nm+1 to n).
I suggest you read the site:
Http://ipsc.ksp.sk/problems/ipsc1999/sol_d.php
Bye,
RED SCORPION

 New poster
 Posts: 6
 Joined: Thu Apr 17, 2003 1:06 pm
10212
Hello, i donot know why this program is TLE ?.
Is there anybody to help me.
sory for the code.
if my algorithm is wrong tell me the right one.
here is the code:

#include<stdio.h>
long mod(long h)
{
while(h%10==0)
{
h/=10;
if(h==0)break;
}
return h%10;
}
int main()
{
long n,m,i,sum,temp;
while(2==scanf("%ld%ld",&n,&m))
{
sum=mod(n);
for(i=1;i<m;i++)
{
n;
sum=mod(sum*mod(n));
}
if(!n!m)sum=1;
printf("%ld\n",sum);
}
return 0;
}
Is there anybody to help me.
sory for the code.
if my algorithm is wrong tell me the right one.
here is the code:

#include<stdio.h>
long mod(long h)
{
while(h%10==0)
{
h/=10;
if(h==0)break;
}
return h%10;
}
int main()
{
long n,m,i,sum,temp;
while(2==scanf("%ld%ld",&n,&m))
{
sum=mod(n);
for(i=1;i<m;i++)
{
n;
sum=mod(sum*mod(n));
}
if(!n!m)sum=1;
printf("%ld\n",sum);
}
return 0;
}
10212
i tried to solve the problem in purely brute force style . but i am not sure it works properly . it is fetching me wa .can u tell me why ?????
[c]#include<stdio.h>
int lastDigit(long int n, long int m){
long int temp,i;
long int mult;
int x;
temp=nm;
mult=1L;
for(i=n;i>temp;i){
mult*=i;
mult=mult%100000;
}
while(mult>0){
x=mult%10;
if(x!=0)
return x;
else
mult/=10;
}
return 0;
}
int main(){
long int n , m;
while(scanf("%ld %ld",&n,&m)==2){
printf("%d\n",lastDigit(n,m));
}
return 0;
}[/c]
is there any efficient algorithm than this ? if ther exists any efficient algo than this , than pliz let me know .
Bye
Riyad
[c]#include<stdio.h>
int lastDigit(long int n, long int m){
long int temp,i;
long int mult;
int x;
temp=nm;
mult=1L;
for(i=n;i>temp;i){
mult*=i;
mult=mult%100000;
}
while(mult>0){
x=mult%10;
if(x!=0)
return x;
else
mult/=10;
}
return 0;
}
int main(){
long int n , m;
while(scanf("%ld %ld",&n,&m)==2){
printf("%d\n",lastDigit(n,m));
}
return 0;
}[/c]
is there any efficient algorithm than this ? if ther exists any efficient algo than this , than pliz let me know .
Bye
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN
Hello, RED SCORPIONRed Scorpion wrote:Andrey, I got it in less then 1 sec.
I suggest you read the site:
Http://ipsc.ksp.sk/problems/ipsc1999/sol_d.php
Bye,
RED SCORPION
according to the site above, I know the last nonzero digit on n!
But the question is p(n,m)=n!/(nm)!
the division is not unique ,
eg. we know the last nonzero digit of n! is 8 , the last nonzero digit of
(nm)! is 2, we can't know the answer is 4 or 9.
How to solve the question?
Could you give me some hints, thx

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
Hi, Windows2k.
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...
Best Regards,
RS
We must factorize n! into this form: 2^i * 3^j * 5^k * 7^l, and find the corresponding i, j, k, and l.But the question is p(n,m)=n!/(nm)!
the division is not unique ,
eg. we know the last nonzero digit of n! is 8 , the last nonzero digit of
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...
Best Regards,
RS
10212 Help!
Why WA?
Please give me some tests for this problem.
[pascal]
program p10212;
{$APPTYPE CONSOLE}
uses
SysUtils;
const two: array[1..4] of byte=(2,4,8,6);
var k,y,n5,n2,n,m,i,g: longint;
begin
while not eof(input) do
begin
readln(n,m);
m:=nm+1; y:=1; n2:=0; n5:=0;
while m<>n+1 do
begin
k:=m;
while k mod 10=0 do begin inc(n5); inc(n2); k:=k div 10; end;
while k mod 5=0 do begin inc(n5); k:=k div 5; end;
while k mod 2=0 do begin inc(n2); k:=k div 2; end;
y:=y*k;
if y div 10>0 then y:=y mod 10;
inc(m);
end;
n2:=n2n5;
if n2>0 then
begin
if n2 mod 4=0 then g:=4
else g:=n2 mod 4;
y:=y*two[g];
if y div 10>0 then y:=y mod 10;
end
else if n2<>0 then begin
y:=y*5;
while y mod 10=0 do y:=y div 10;
y:=y mod 10;
end;
writeln(y)
end;
end.
[/pascal]
Please give me some tests for this problem.
[pascal]
program p10212;
{$APPTYPE CONSOLE}
uses
SysUtils;
const two: array[1..4] of byte=(2,4,8,6);
var k,y,n5,n2,n,m,i,g: longint;
begin
while not eof(input) do
begin
readln(n,m);
m:=nm+1; y:=1; n2:=0; n5:=0;
while m<>n+1 do
begin
k:=m;
while k mod 10=0 do begin inc(n5); inc(n2); k:=k div 10; end;
while k mod 5=0 do begin inc(n5); k:=k div 5; end;
while k mod 2=0 do begin inc(n2); k:=k div 2; end;
y:=y*k;
if y div 10>0 then y:=y mod 10;
inc(m);
end;
n2:=n2n5;
if n2>0 then
begin
if n2 mod 4=0 then g:=4
else g:=n2 mod 4;
y:=y*two[g];
if y div 10>0 then y:=y mod 10;
end
else if n2<>0 then begin
y:=y*5;
while y mod 10=0 do y:=y div 10;
y:=y mod 10;
end;
writeln(y)
end;
end.
[/pascal]

 New poster
 Posts: 16
 Joined: Tue Dec 03, 2002 9:44 pm
explain
Scorpion,
Can you explain your idea for input : 25 6
Can you explain your idea for input : 25 6