10515 - Powers Et Al.

[pavelph]

I know the trick of finding the repeated sequence of [the last digit of m] poweres n to get the same correct answer, but could anyone please explain why the last two digits of n is enough?

You can explain (on paper) that all periods of last digit are 1, 2 or 4 - for different digit. And it is enough to find (m mod 4) to find last digit of n^m;
Master proved in last subject that (m mod 4) = ((m mod 100) mod 4).

I hope it helps you.

[pavelph]

Hi! I have program that give me right output for input from osan.
But judge give me WA.
One question: can I read m and n in double variable or I must to read it as string (m, n<10^101) ?

[osan]

ya you are right. you have to read m & n as a string. u cann't hold a 10^101 number in double.

just remember

1235483654865224%4=0
24%4=0

so you can only use last digit of string m & last 2 digit of string n.


anyway sorry cause i didn't give any large input in my input set that why it was confusing for you.

hope you will get AC now.

GOOD LUCK

[Riyad]

hey ,
i am getting wa in 10515 . i used string to take input and considered the last digit of the base and the last two digit of power . but to my surprise i am getting WA ......

plizzzzzzzzzzzz some one check the code for me .

[cpp]# include <stdio.h>
# include <string.h>
# include <stdlib.h>

long int a,b ;

char r[1000],s[1000];



void Process(){

if(strlen(s)<=9 && strlen(r)<=9){

a=atol(r);
b=atol(s);
return ;
}


a=r[strlen(r)-1]-48;

b=s[strlen(s)-1]-48 ;

if(strlen(s)>1)
b+=10*(s[strlen(s)-2]-48);
else
return ;

}

int main(){



int x,y;

while(scanf("%s %s",r,s)==2){

Process();

if(a==0L && b==0L)break;

x=a;


if(b==0L){
printf("1\n");
continue;
}

if(x==0 || x==1 || x==5 || x==6){
printf("%d\n",x);
continue;
}

else{

if(x==2L){

x=b%4;

if(x==0)printf("6\n");
else if(x==1)printf("2\n");
else if(x==2)printf("4\n");
else if(x==3)printf("8\n");

continue;
}

else if(x==3L){

x=b%4;

if(x==0)printf("1\n");
else if(x==1)printf("3\n");
else if(x==2)printf("9\n");
else if(x==3)printf("7\n");

continue;
}

else if(x==4L){

y=b%2;
if(y==0)
printf("6\n");
else
printf("4\n");
continue;
}

else if(x==7L){

x=b%4;

if(x==0)printf("1\n");
else if(x==1)printf("7\n");
else if(x==2)printf("9\n");
else if(x==3)printf("3\n");

continue;

}

else if(x==8L){

x=b%4;
if(x==0)printf("6\n");
else if(x==1)printf("8\n");
else if(x==2)printf("4\n");
else if(x==3)printf("2\n");

continue;
}

else if(x==9L){

y=b%2;

if(y==0)
printf("1\n");
else
printf("9\n");

continue;
}

}
}


return 0;
}[/cpp]

i must have made some stupid mistake .pliz help me in this .
Riyad

[minskcity]

I got WA with this code... Am I missing something? Thx in advance[cpp]#include <iostream>
#include <string>
//#include <fstream>
using namespace std;

string s1, s2;
long t, ans, p;

int main(){

// ifstream cin("in.txt");

while(cin >> s1 >> s2 && !(s1[0] == '0' && s2[0] == '0')){
ans = 1;
p = s1[s1.size() - 1] - '0';
t = s2[s2.size() - 1] - '0';
if(s2.size() > 1) t += 10 * (s2[s2.size() - 2] - '0');

while(t != 0){
if(t%2) ans = (p*ans)%10;
p = (p*p)%10;
t /= 2;
}

cout << ans << endl;
}

return 0;
}
[/cpp]

[minskcity]

Never mind - almost that one was almost correct [cpp]#include <iostream>
#include <string>
using namespace std;

string s1, s2;
long t, ans, p;

int main(){

while(cin >> s1 >> s2 && !(s1[0] == '0' && s2[0] == '0')){
ans = 1;
p = s1[s1.size() - 1] - '0';
t = s2[s2.size() - 1] - '0';
if(s2.size() > 1) t = (t + (s2[s2.size() - 2] - '0')*10)%4 + 4;

while(t != 0){
if(t%2) ans = (p*ans)%10;
p = (p*p)%10;
t /= 2;
}

cout << ans << endl;
}
return 0;
}
[/cpp]

[Badsha of DIU]

Dear friends I face a problem
with 10515 . I solve it but it is now
in "Time limite exceeded"
So help me if possible.
waiting for your reply

Here is my code:

# include <stdio.h>
# include <math.h>

double m,n;
long res;
main()
{
while(scanf("%lf %lf",&m,&n)==2)
{
if(m==0 & n==0)
break;
else
{
res=m;
for(int i=1;i<n;i++)
{
res=res*m;
res=res%10;
}
printf("%ld\n",res);
}
}
return 0;
}

[sohel]

A line from the problem statement.

The input file contains less than 100000 lines. Each line contains two integers m and n (Less than 10^101). Input is terminated by a line containing two zeroes. This line should not be processed.

consider the input:
10^100 10^100

and take a look at this part of your code :
[c]
for(int i=1;i<n;i++)
{
res=res*m;
res=res%10;
}
[/c]

The complexity of your code will be :

O(10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)

And I don't think this will pass time limit.

[Badsha of DIU]

Now what will be the solution?
how I reduce this complexity.
waiting for your reply

[shamim]

Well, evaluate the first few powers and you will see some pattern.

e.g

2^1 =2 -->2
2^2 = 4-->4
2^3=8-->8
2^4=16-->6
2^5=32-->2
2^6=64-->4
2^7=128-->8
2^8=256-->6
.
.
.
.

Notice the pattern..

similar pattern exists for other numbers.

[Badsha of DIU]

Thank you Shamim Bahi .
You give me good solution
I will try to solve this problem by
your given information.
Thank you very much

[oulongbin]

this is my code,thx;
[cpp]
#include <iostream.h>
#include <string.h>
#include <stdio.h>
#include <cmath>

int main()
{
char a[110],b[110];
int m,n;
int len;

while(cin>>a>>b)
{
if(!strcmp(a,"0")&&!strcmp(b,"0"))
break;
m=n=0;
len=strlen(a);
if(len==1)
m=(int(a[len-1])-48);
else
m=(int(a[len-2])-48)*10+(int(a[len-1])-48);
len=strlen(b);
if(len==1)
n=(int(b[len-1])-48);
else
n=(int(b[len-2])-48)*10+(int(b[len-1])-48);
if(n==0)
cout<<1<<endl;
else
{
while(n>4)
n-=4;
cout<<int(pow(m,n))%10<<endl;
}
}
return 0;
}
[/cpp]

[udvat]

i failed to understand your logic.but I can tell you how i solved this problem.you can get more help by browsing the topics in this forum on p-10515.

1.one digit of m & two digits of n is required.

2. the only one digit of m can be any digit from 0-9

3.try to find out 0^i to 9^i,obviously you will find a repetating cycle
e.g for 2,the cycle is 2 4 8 6

4. two[]={6,2,4,8}

for example m=2 & n=100
index=100%4=0
two[0]=6
so the last digit of 2^100 is 6

hope this will help you.

[murtaza]

I don't think u have got the logic right for solving the problem.
Ur program gives wrong result for even inputs like
2 7

[Sedefcho]

I cover all these test cases above ( given by osan ) and still
I get WA.
I have the feeling there's something tricky here.

What should be the output for 4000 ^ 0 ---> 1 or 0 ?!

In this case lastDigit(M) is 0

Same quesiton for 404040412 ^ 0 ---> 0 or 1 ?!

In this case lastDigit(M) is NOT 0