## 10515 - Powers Et Al.

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

Moderator: Board moderators

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg
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
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

### Question about double.

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
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Location: Bangladesh,Dhaka.
Contact:

### must use string

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 this time WA
what next...............?

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

### plizzz some one help me

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,s;

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

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
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' && s2 == '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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
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' && s2 == '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
New poster
Posts: 3
Joined: Mon Nov 03, 2003 5:36 pm
Location: Bangladesh
Contact:

### 10515

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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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
New poster
Posts: 3
Joined: Mon Nov 03, 2003 5:36 pm
Location: Bangladesh
Contact:
Now what will be the solution?
how I reduce this complexity.
waiting for your reply

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
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
New poster
Posts: 3
Joined: Mon Nov 03, 2003 5:36 pm
Location: Bangladesh
Contact:
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
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

### 10515 I always got WA,please help.

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

int main()
{
char a,b;
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
New poster
Posts: 29
Joined: Thu Aug 07, 2003 9:56 pm

### 10515-reply

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=6
so the last digit of 2^100 is 6

hope this will help you.

murtaza
New poster
Posts: 7
Joined: Tue Jul 20, 2004 7:42 pm
Location: India
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
Putting n programmers on a problem will not result in the time of solving the problem to reduce by n.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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