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
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
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:
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
this time WA
what next...............?
Riyad
Experienced poster
Posts: 131 Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:
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
[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:
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;
}
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
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..
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
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
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.
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