10212 - The Last Non-zero Digit.

[Andrey Mokhov]

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]

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

Please Answer Me ..
Thanks

[Andrey Mokhov]

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]

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]

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]

Thanks, Thanks very much Andrey, Now I got AC.
I am waiting for any help from you everytime.

Best Regards,
RED SCORPION

[Andrey Mokhov]

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.

Buy.
Andrey.

[Red Scorpion]

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)]

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;
}

[Riyad]

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
Riyad

[windows2k]

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]

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]

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:=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]

Scorpion,

Can you explain your idea for input : 25 6

[Tompik]

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?