10212 - The Last Non-zero Digit.

[ezaztime]

Code: Select all

int main()
{
	//freopen("10212.in","r",stdin);
	unsigned n,m;
	while(cin>>n && cin>>m)
	{
		unsigned int f1=n;
		if(f1==0)
			f1=1;
		for(unsigned int i=1;i<n;i++)
		{
			f1=f1*i;
		}
		unsigned int f2=n-m;
		if(f2==0)
			f2=1;

		for(i=1;i<n-m;i++)
		{
			f2=f2*i;
		}
		unsigned int f=f1/f2;		
		if(f%10!=0)
		{
			f=f%10;
		}
		else
		{
			while(f%10==0)
			{
				f=f/10;
			} 
			f=f%10;
		}
		cout<<"f : "<<f<<endl;
	}
	return 0;
}

it gives the correct result when i myself test it ...

any body please help to find out the bug...

[sapnil]

Code: Select all

for(unsigned int i=1;i<n;i++) 
{ 
f1=f1*i; 
}

Here you find n!, but n<=20000000

>> Hope it help

Thanks
Keep posting
Sapnil

[iggy]

I still wonder how people get this calculated in under 0.002s..

What worked for me was to first cache pairs (c, d) for every x: 1..20'000'000 such that
x = 2^a * 5^b * r;
c = a - b; // easily calculated
d = r % 10;

Then considering:
if x -> (c, d) then lastnonzerodigit(x) = { d, if c = 0 | 5, if c<0 | (d*2^c) % 10, if c > 0 }
if x -> (c1, d1) and y -> (c2, d2) then x*y -> (c1+c2, (d1*d2) % 10)

And given N and M, we are interested in last non-zero digit of
N*(N-1)*...*(N-M+1) -> (c1 + c2 + ... + cm-1, (d1 * d2 * ... dm-1) % 10)

But this barely makes it in time (9.5s).

I've tried the prime factorization of N! and (N-M)! but didn't fit in time.. What's the trick to calculating this problem fast?

[Chirag Chheda]

Can someone plz give me test cases so that i can find the bug in my code
Thnx in advance

[Jan]

I am asking why it should work?

Code: Select all

b %= 20000000;

[Chirag Chheda]

ok now i got it
well my approach was completely wrong at it.
I think now i shud give it a try

[Sedefcho]

To iggy:

I also don't know how some people solved this one in less than 0.010 secs
but (if they used a fair algorithm) I guess they tried to generate the numbers
instead of iterating through them. What do I mean? Well...

My algorithm runs in 3.710 secs and is implemented in C++.

Some small hints about it.

1. Each natural number N can be represented as N = (2^a) * (5^b) * r
where GCD(r,2)=1 and GCD(r,5)=1 and a>=0 and b>=0.
Now if you precalculate a,b,r for N=1 to 20 million things get
much simpler. And if you use the cached values calculated above
an O(N-M) algorithm (for each test case) will pass the time limit for sure.

2. Use modular exponentiation which runs in O(log K) where K is the degree.
I mean for example if you want to calculate ( 2 ^ 1000 ) % 10 this can be done
easily in O(log 1000) time.

Even these two simple observations can take your program
to about 3.800 - 4.000 secs runtime for the judge input
(this remark is valid as of August 26, 2008).

[stcheung]

Let me summarize the method to not get TLE:
(1) For each number in the loop (eg. [8, 7, 6] if you are calculating P_8_3), calculate it as 2^a * 5^b * c
(2) Keep a running sum of the a & b above. You can simply use a variable, add a and subtract b from it in each iteration
(3) After you figure out c in each iteration, do c % 10. Keep track of all these c %10. Each this example, you would end up with one 7 and one 3
(4) Multiply all these c % 10 together. I don't mean it literally because that's way too slow. You should be able to quickly calculate the final digit when multiplying say ten thousand 3s together. Observe the last digit pattern 3, 9, 7, 1, 3... Then multiply the effect of the running sum in (2). If there's more 2 than 5, your running sum would be positive and you have to what's the digit for multiplying all these 2 together. Similarly if there's more 5 than 2.
(5) If you only do (1)-(4), there's great chance you still get TLE. In that case, you need to have a cache so you can figure out the running sum and the c % 10 directly. Use byte (or whatever is the smallest integer size in your language) to store these so you won't have OutOfMemory error.

My Java program got AC under 6 sec so if you do all these you should get AC well under the TLE limit.

[Shafaet_du]

sample:

Code: Select all

100 10
200000 34
        453434 23
  5656565 343
546433 2334
   123123 1
45546 934
1 1
122342 12

Code: Select all

2
4
8
8
4
3
4
1
8

[Dominik Michniewski]

Finally I got it solved :)

I got 4,3s time (in the middle of all users, which solved this problem).
My only mistake was improper handling of integer overflow :(:(

Best regards
DM

[najim_ju]

Plz,Help me to figure out why i am getting WA???what is correct or more efficient approach to this problem?<sorry,i m a naive user...so i may not gave the post in correct approach>

Code: Select all

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
#define max 20000100
#define MOD 100000000

int check[max+2];
int prime[max+2];
void generate_prime();

int LND(int b,int p);

int main()
{
generate_prime();
//freopen("inp.txt","r",stdin);
int n,r,k;
while(scanf("%d %d",&n,&r)==2)
	{
	long long int a=1;
	int R=n-r;
	int i=0;
	int ct_n=0,ct_d=0,ct_2n=0,ct_2d=0,ct_5n=0,ct_5d=0;
	int N=n;
	int D=R;
	for(i=0;prime[i]<=n;i++)
		{
		ct_n=0,ct_d=0;
		N=n;
		if(prime[i]<=R)D=R;
		else D=0;
		if(prime[i]!=2 && prime[i]!=5)
			{
			while(N)
				{
				ct_n+=N/prime[i];
				N/=prime[i];
				}
			while(D)
				{
				ct_d+=D/prime[i];
				D/=prime[i];
				}
			ct_n=ct_n-ct_d;
			a=(a*LND(prime[i],ct_n))%MOD;
			}
		else if(prime[i]==2)
			{
			while(N)
				{
				ct_2n+=N/prime[i];
				N/=prime[i];
				}
			while(D)
				{
				ct_2d+=D/prime[i];
				D/=prime[i];
				}
			ct_2n=ct_2n-ct_2d;
			}
		else if(prime[i]==5)
			{
			while(N)
				{
				ct_5n+=N/prime[i];
				N/=prime[i];
				}
			while(D)
				{
				ct_5d+=D/prime[i];
				D/=prime[i];
				}
			ct_5n=ct_5n-ct_5d;
			ct_2n=ct_2n-ct_5n;
			ct_5n=0;
			a=(a*LND(2,ct_2n))%MOD;
			}
		//i++;
		}
	printf("%d\n",a%10);
	}
return 0;
}

void generate_prime()
{
long i,j,c=0;
for(i=2;i<=max;i++) check[i]=1;
for(i=2;i<=sqrt(max);  )
	{
	for(j=i+i;j<=max;j+=i)check[j]=0;
	i++;
	for( ;!check[i];i++);
	}
j=0;
for(i=2;i<max;i++) 
	{
	if(check[i]==1)prime[j++]=i;
	}
}

int LND(int b,int p)
{
b=b%10;
if(p==0)return 1;
else if(p%4==1)return b;
else if(p%4==2)return (b*b)%10;
else if(p%4==3)return (b*b*b)%10;
else if(p%4==0)return (b*b*b*b)%10;
}

[plamplam]

I am yet to get Accepted in this problem-.- I tested my code with several large random numbers and compared my output against uvatoolkit. I handled cases where n or m is 0 and although my brute force algorithm sucks, it should not, by any means, get Wrong Answer. Okay enough yelling, here are some randomly generated inputs which I used. The outputs are from uvatoolkit:

Code: Select all

2727310 169580
8410985 7364225
8717510 8305150
8945955 462075
3639260 575840
7979410 7261440
8712325 2794105
1290455 520940
7459080 2953620
9049655 6955220
7083015 6821020
775920 732000
9607805 6956135
2586400 2221620
8548540 6113725
9082290 1976705
7639335 5434795
7301395 4031185
8308200 7609140
8703480 4603060
6961930 817400
9046300 8192605
9256140 3110085
6224440 2864255
3983910 1580510
8750755 3867400
5557100 4057720
8632415 3843000
9162200 6306790
8079755 1887950
6703900 3342495
8501570 5023045
2784955 2540345
4175145 1521950
3323585 2860290
9673685 8819075
7444745 6355285
7715280 1382870
9452255 2078880
5481155 2113955
5374710 4711030
5205130 3641395
9584320 9373565

Code: Select all

2
6
2
8
4
2
2
4
6
4
6
6
6
2
2
8
8
6
8
4
6
4
4
2
8
2
2
2
6
8
8
4
4
4
8
8
2
2
2
6
2
8
6

[X123]

i solved uva 568 to find out the last non zero digit of n!
and got accepted. here is my code

Code: Select all

#include<stdio.h>
#define max 20000000
#define lmt 4473

unsigned flag[max>>6];

#define ifc(n) (flag[n>>6]&(1<<((n>>1)&31)))
#define isc(n) (flag[n>>6]|=(1<<((n>>1)&31)))
int power(int prime,int n)
{
	int a=n;
int pow=0;
while(a!=0)
{
	pow=a/prime+pow;
	a=a/prime;
}
return pow;
}
int main()
{
	int index[3][4]={{6,2,4,8},{1,3,9,7},{1,7,9,3}};
	int i,j,k,n,twos,fives,digittwo,threes,p,sevens,digitthree,digitseven,lastdigit;
	for(i=3;i<lmt;i+=2)
		if(!ifc(i))
		for(j=i*i,k=i<<1;j<max;j+=k)
		isc(j);
while(scanf("%d",&n)==1)
{
	if(n==0||n==1)
		printf("%5d -> 1\n",n);
else

{
twos=power(2,n);

fives=power(5,n);
twos=(twos-fives)%4;
digittwo=index[0][twos];
threes=power(3,n);
sevens=power(7,n);
for(i=11;i<=n;i+=2){
	if(!ifc(i))
{
	p=i%10;
	int c=power(i,n);
	if(p==7)
		sevens=sevens+c;
	else if(p==3)
		threes=threes+c;
	else if(p==9)
		threes=threes+2*c;
}
}
threes=threes%4;
digitthree=index[1][threes];
sevens=sevens%4;
digitseven=index[2][sevens];

lastdigit=(digittwo*digitseven*digitthree)%10;
printf("%5d -> %d\n",n,lastdigit);

}

}
	return 0;
}
 then i modified this code for 10212. but getting WA.. can anybody help me?  :-? 


#include<stdio.h>
#define max 20000100
#define lmt 4473

unsigned flag[max>>6];

#define ifc(n) (flag[n>>6]&(1<<((n>>1)&31)))
#define isc(n) (flag[n>>6]|=(1<<((n>>1)&31)))
int power(int prime,int n)
{
	int a=n;
int pow=0;
while(a!=0)
{
	pow=a/prime+pow;
	a=a/prime;
}
return pow;
}
int main()
{
	int index[3][4]={{6,2,4,8},{1,3,9,7},{1,7,9,3}};
	int i,j,k,n,twos,fives,digittwo,threes,p,sevens,digitthree,digitseven,lastdigit,u;
	for(i=3;i<lmt;i+=2)
		if(!ifc(i))
		for(j=i*i,k=i<<1;j<max;j+=k)
		isc(j);
while(scanf("%d %d",&n,&u)==2)
{
	if(n==0||n==1||u==0)
		printf("1\n");
		else if(u==1){
				while(n%10==0)
				n=n/10;
			printf("%d\n",n%10);
		}
else
{
	u=n-u;
twos=power(2,n)-power(2,u);

fives=power(5,n)-power(5,u);
twos=(twos-fives)%4;
digittwo=index[0][twos];
threes=0;
sevens=0;
for(i=3;i<=n;i+=2){
	if(!ifc(i))
{
	p=i%10;
	if(p==7||p==3||p==9){
	int c=power(i,n)-power(i,u);
	if(p==7)
		sevens=sevens+c;
	else if(p==3)
		threes=threes+c;
	else if(p==9)
		threes=threes+2*c;
	}
}
}
threes=threes%4;
digitthree=index[1][threes];
sevens=sevens%4;
digitseven=index[2][sevens];
lastdigit=(digittwo*digitseven*digitthree)%10;
printf("%d\n",lastdigit);

}

}
	return 0;
}

[brianfry713]

Input 7 3, output should be 1

[dibery]

Some more cases

Input:
15 1
15 2
15 3
15 4

Output:
5
1
3
6