10515 - Powers Et Al.

[r.z.]

already correct that! Thanks

but my program is still taking to much time....

Is there any method to make it more efficient?

thanks before

[shamim]

Each line contains two integers m and n (Less than 10^101).

Here is a part from your code

;
for(i=0;i<n;i++)
{ temp=(int)m%10;
digit*=(int)temp;
digit=digit%10;
}

I guess you should realize that this loop will take far too long for the worst case of n=10^101-1.

[technogeek]

Allright here's a hint......
Do you really have to carry out the multiplications to find the last digit ?

Example : 9^1 = 9
9^2 = ..1
9^3 = ..9
9^4 = ..1

etc. where .. denotes digits other than last digit.

[r.z.]

There's a pattern.....

thanks for all your explenation, I really appriciate it.

[r.z.]

I've tried almost all cases but the judge gave me WA.....

[c]
#include<stdio.h>
#include<string.h>

void main()
{ char m[101],n[101];
int arr[4];
int p1,p2,m1,n1,i,t;
while(1)
{ m1=0;
n1=0;
scanf("%s %s",m,n);
if(m[0]=='0' && n[0]=='0') break;
p1=strlen(m);
p2=strlen(n);
m1=m[p1-1]-48;

n1+=n[p2-1]-48;
if(p2>1)
n1+=(n[p2-2]-48)*10;

m1=m1%10;
n1=(n1-1)%4;
t=1;
for(i=0;i<4;i++)
{ t*=m1;
arr=t;
}
if(p2==1 && n[p2-1]=='0')
arr[0]=1;
printf("%d\n",arr[n1]%10);
}
}
[/c]

[miras]

your program looks OK .......

[Zhao Le]

I don't know what's wrong about my code.

I have test a lot, thus don't got lost.

Who can help me, thanks in advance.

[cpp]#include <iostream>
#include <string.h>

using namespace std;

int const Max1=101;
int const Max2=4; // at most 4 different case

char A[Max1];
char B[Max1];
int S[Max2];

void main()
{
int i;
for(i=0;i<Max1;i++) // clear stage
A=B=NULL;
for(i=0;i<Max2;i++)
S=0;
while(1)
{
cin>>A>>B;
int a=0;
while(A[a]!=NULL)
a++;
int length_m=a;
a--;
int m=A[a]-'0';
a=0;
while(B[a]!=NULL)
a++;
int length_n=a;
a-=2;
int n;
if(B[a]>'0'&&B[a]<='9')
n=(B[a]-'0')*10+(B[a+1]-'0');
else
n=(B[a+1]-'0');
if(m==0&&n==0&&length_m==1&&length_n==1) break;
else if(m==0&&n==0&&length_m>1)
{
cout<<'0'<<endl;
continue;
}
else if(n==0)
{
cout<<'1'<<endl;
continue;
}
int cnt=m;
int k=0;
int i,j;
for(i=0;i<Max2;i++)
{
if(m>0) m%=10;
if(!S[0]&&m!=S[0]) S[0]=m;
else if(!S[1]&&m!=S[1]) S[1]=m;
else if(!S[2]&&m!=S[2]) S[2]=m;
else if(!S[3]&&m!=S[3]) S[3]=m;
m*=cnt;
}
for(j=0;j<Max2;j++)
if(S[j]) continue;
cout<<S[(n-1)%j]<<endl;
for(a=0;a<Max1;a++) // clear stage
A[a]=B[a]=NULL;
for(a=0;a<Max2;a++)
S[a]=0;
}
}[/cpp]

[Zhao Le]

Anyone help me!

I'm crazy!!!!

[gawry]

Anyone help me!

I'm crazy!!!!

Try this input:
10 0
0 0

[Zhao Le]

Try this input:
10 0
0 0

I have solved this bug.

But when I sumbit to the judge, I was suprised to see it is still WA.

So there is something wrong with my code.

Here is my new code.

[cpp]#include <iostream.h>

int const Max1=101;
int const Max2=4; // at most 4 different case

char A[Max1];
char B[Max1];
int S[Max2];

void main()
{
int i;
for(i=0;i<Max1;i++) // clear status
A=B=NULL;
for(i=0;i<Max2;i++)
S=0;
while(1)
{
cin>>A>>B;
int a=0;
while(A[a]!=NULL)
a++;
int length_m=a;
a--;
int m=A[a]-'0'; // last digit of M
a=0;
while(B[a]!=NULL)
a++;
int length_n=a;
a-=2;
int n;
if(B[a]>'0'&&B[a]<='9')
n=(B[a]-'0')*10+(B[a+1]-'0'); // last two digit of N
else
n=(B[a+1]-'0');// last digit of N
if(m==0&&n==0&&length_m==1&&length_n==1) break; // case 0 0
else if(n==0&&length_n==1) // case X 0
{
cout<<'1'<<endl;
continue;
}
int cnt=m;
int k=0;
int i,j;
for(i=0;i<Max2;i++) // At most four cases
{
if(m>0) m%=10;
if(!S[0]&&m!=S[0]) S[0]=m;
else if(!S[1]&&m!=S[1]) S[1]=m;
else if(!S[2]&&m!=S[2]) S[2]=m;
else if(!S[3]&&m!=S[3]) S[3]=m;
m*=cnt;
}
for(j=0;j<Max2;j++)
if(S[j]) continue;
cout<<S[(n-1)%j]<<endl;
for(a=0;a<Max1;a++) // clear status
A[a]=B[a]=NULL;
for(a=0;a<Max2;a++)
S[a]=0;
}
}[/cpp]

Can someone give me test case!

Thanks in advance.

[gawry]

Can someone give me test case!

Thanks in advance.

Here's another one:

12 100
0 0

[Zhao Le]

Finally, I got AC.

There is not words can express my thanks.

[udvat]

wud anyone plz help me to understand the logic of powers et all?
i took the last digit of base and the last two digits of power.it works fine for many inputs,but in case of 2^100 it gives the output 0,whereas the correct output is 6.plz help me

[UFP2161]

Well, what's the last digit of 2^99? .. If you multiply that digit by two (thus getting 2^100), you will get 6, and definitely not 0 (unless 2^99 had a last digit of 0, and 2^98, etc, which you know is not the case).

Now, you should ask yourself, is taking the last two digits enough when the last two digits are equivalent to '00'?

[Dmytro Chernysh]

Eric, can you post a huge test input/output file? I'm getting WA all the times, but my solution DOES passes all the inputs here.