10212 - The Last Non-zero Digit.

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Andrey Mokhov
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.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
What do tou mean by
"(!tp&1) instead of !(tp%2) and similiary tp>>=1 instead of tp/=2"

" Count2 is always >= Count5 ":

how if "nPm" = 26P2 :

26!
------ = 25 * 26 = (5*5) * (2*13)
24!

count5 = 2 and count2=1

Thanks

Andrey Mokhov
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.

Red Scorpion
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. Red Scorpion
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. Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
Thanks, Thanks very much Andrey, Now I got AC.
I am waiting for any help from you everytime.

Best Regards,
RED SCORPION

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
Well, I'm still not satisfied with my solution. And I know how to improve it.

It will be some precomputing. We can calculate the last digits of multiplications of numbers from 100*k to 100*k+99 for each k. And then it won't be necessary to do it every time we read in new testcase. Andrey.

Red Scorpion
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 n-m+1 to n).

I suggest you read the site:
Http://ipsc.ksp.sk/problems/ipsc1999/sol_d.php

Bye,
RED SCORPION

Harun (IIUC)
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;
}

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

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=n-m;
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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
Red 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
Hello, RED SCORPION
according to the site above, I know the last non-zero digit on n!
But the question is p(n,m)=n!/(n-m)!
the division is not unique ,
eg. we know the last non-zero digit of n! is 8 , the last non-zero digit of
(n-m)! is 2, we can't know the answer is 4 or 9.
How to solve the question?
Could you give me some hints, thx Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
Hi, Windows2k.   But the question is p(n,m)=n!/(n-m)!
the division is not unique ,
eg. we know the last non-zero digit of n! is 8 , the last non-zero digit of
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...

Best Regards,
RS Tompik
New poster
Posts: 3
Joined: Mon Jan 26, 2004 6:37 pm

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
m:=n-m+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:=n2-n5;
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]

Shahriar Nirjon
New poster
Posts: 16
Joined: Tue Dec 03, 2002 9:44 pm

explain

Scorpion,

Can you explain your idea for input : 25 6

Tompik
New poster
Posts: 3
Joined: Mon Jan 26, 2004 6:37 pm

10212

Who can tell me what does it mean: "Each line of the input file contains two integers N (0<=N<=20000000), M (0<=N)". How much M will be?