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

Post Reply
pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

Post by pavelph » Sat Jan 24, 2004 11:48 pm

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.

Post by pavelph » Mon Feb 02, 2004 8:16 am

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

Post by osan » Mon Feb 02, 2004 11:55 am

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

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

plizzz some one help me

Post by Riyad » Sun Feb 15, 2004 4:44 pm

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
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

Post by minskcity » Fri Jun 04, 2004 4:14 am

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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Fri Jun 04, 2004 6:07 am

Never mind - almost that one was almost correct :lol: [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
New poster
Posts: 3
Joined: Mon Nov 03, 2003 5:36 pm
Location: Bangladesh
Contact:

10515

Post by Badsha of DIU » Tue Oct 05, 2004 9:34 am

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;
}

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Tue Oct 05, 2004 10:50 am

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:

Post by Badsha of DIU » Wed Oct 06, 2004 6:28 am

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

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Wed Oct 06, 2004 9:09 am

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.. :wink:

similar pattern exists for other numbers.

Badsha of DIU
New poster
Posts: 3
Joined: Mon Nov 03, 2003 5:36 pm
Location: Bangladesh
Contact:

Post by Badsha of DIU » Wed Oct 06, 2004 9:26 am

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.

Post by oulongbin » Thu Oct 28, 2004 6:06 am

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
New poster
Posts: 29
Joined: Thu Aug 07, 2003 9:56 pm

10515-reply

Post by udvat » Fri Oct 29, 2004 11:58 am

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
New poster
Posts: 7
Joined: Tue Jul 20, 2004 7:42 pm
Location: India

Post by murtaza » Sun Nov 07, 2004 5:51 pm

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.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Mon Feb 14, 2005 5:38 pm

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

Post Reply

Return to “Volume 105 (10500-10599)”