## 10515 - Powers Et Al.

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

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
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...............?
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 .
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]
New poster
Posts: 3
Joined: Mon Nov 03, 2003 5:36 pm
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.

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.
New poster
Posts: 3
Joined: Mon Nov 03, 2003 5:36 pm
Contact:
Now what will be the solution?
how I reduce this complexity.
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.
New poster
Posts: 3
Joined: Mon Nov 03, 2003 5:36 pm
Contact:
Thank you Shamim Bahi .
You give me good solution
I will try to solve this problem by
Thank you very much oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

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

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

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