10515  Powers Et Al.
Moderator: Board moderators
think abt this
Dear bayzid
i think it would be tuff for you to handle last two digit or or last digit. after getting input as a string.
i hope u know about the function strlen.
try to use this
hope you understand whatever i wanna to say.
if you can't mail me then.
i think it would be tuff for you to handle last two digit or or last digit. after getting input as a string.
i hope u know about the function strlen.
try to use this
hope you understand whatever i wanna to say.
if you can't mail me then.
this time WA
what next...............?
what next...............?
Re: I got AC .
Nope, one digit of m and two digits of n are enough.yan4546 wrote:2 digits is not enough and 3 digits can do .

 Learning poster
 Posts: 54
 Joined: Sun Oct 28, 2001 2:00 am
 Location: Bangladesh
Think about what happens if you calculate m^n. Think about the
manual multiplication steps.
You multiply every digit of m with n. There are some carry propagation
and others. But for the last digit there is no carry or other things. Try
simulating something like 15^15. See how the last digit remains 5^15.
Now we solve the problem of m being too big. But again n is also too big.
Now look at the results of 0^i through 9^i (only last digit). You will see
there is some repeating pattern. To cover all repeating patter with
modulus calculation it is necessary you take the last two digit of n and
then use the repeating pattern to get to solution.
So finally you have for any m, n you can have the result in constant time.
Hope it makes things a little clear.
manual multiplication steps.
You multiply every digit of m with n. There are some carry propagation
and others. But for the last digit there is no carry or other things. Try
simulating something like 15^15. See how the last digit remains 5^15.
Now we solve the problem of m being too big. But again n is also too big.
Now look at the results of 0^i through 9^i (only last digit). You will see
there is some repeating pattern. To cover all repeating patter with
modulus calculation it is necessary you take the last two digit of n and
then use the repeating pattern to get to solution.
So finally you have for any m, n you can have the result in constant time.
Hope it makes things a little clear.
10515 TLE
Hy! I'm getting TLE with this code. Can anyone explain why?
[cpp]
#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;
/*
2 2
2 5
0 0
*/
int main()
{
int m,n;
while(cin>>m>>n)
{
if(!m && !n)
return 0;
if(m==1){
cout<<"1"<<endl;
continue ;
}
if(m==10  m==0){
cout<<"0"<<endl;
continue;
}
int c=0;
int dig=1;
while(c++<n)
{
dig*=m;
if(dig>=10)
dig = digfloor((double)dig/10)*10;
}
cout << dig << endl;
}
return 0;
}
[/cpp]
[cpp]
#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;
/*
2 2
2 5
0 0
*/
int main()
{
int m,n;
while(cin>>m>>n)
{
if(!m && !n)
return 0;
if(m==1){
cout<<"1"<<endl;
continue ;
}
if(m==10  m==0){
cout<<"0"<<endl;
continue;
}
int c=0;
int dig=1;
while(c++<n)
{
dig*=m;
if(dig>=10)
dig = digfloor((double)dig/10)*10;
}
cout << dig << endl;
}
return 0;
}
[/cpp]

 Learning poster
 Posts: 82
 Joined: Thu Oct 10, 2002 1:15 pm
 Location: St. Johns, Canada
 Contact:
Another word here i want to add that a big integer is divisable by 4, only its last two digit is divisable by 4. I mean a big integer such as
.......XX
is divisable by 4, if the number
XX is divisable by 4
I think it will help more
If you want more help then please visit the site
http://www.acmbeginner.tk
or
http://www.geocities.com/acmbeganer/Acm ... Tricks.htm
M H Rasel
CUET Old Sailor
.......XX
is divisable by 4, if the number
XX is divisable by 4
I think it will help more
If you want more help then please visit the site
http://www.acmbeginner.tk
or
http://www.geocities.com/acmbeganer/Acm ... Tricks.htm
M H Rasel
CUET Old Sailor
10515 WA
I have tried lots of test data I could think about.
And I have read the posts about 10515,
but I still can't figure out what's the problem with my code......
Could someone PLS help me ?
thanks a lot......
[cpp]#include <stdio.h>
#include <string.h>
#include <math.h>
int Rich_Mod(char *b,int cycle)
{
int t;
if(cycle==1)
return 1;
if(cycle==2)
return (b[strlen(b)1]'0')%2+2;
if(cycle==4)
{
if(strlen(b)>1)
t = 10*b[strlen(b)2]+b[strlen(b)1];
else
t = b[strlen(b)1];
return t%4+4;
}
}
void main()
{
char a[2000],b[2000];
int Base[10]={0,1,4,4,2,1,1,4,4,2};
int cycle,c;
int mode=0;
while(scanf("%s %s",&a,&b)==2)
{
if(strlen(a)==1 && a[0]=='0' && strlen(b)==1 && b[0]=='0')
break;
if(strlen(b)==1 && b[0]=='0')
printf("1");
else if(strlen(a)==1 && a[0]=='0')
printf("0");
else
{
cycle = a[strlen(a)1]'0';
c = Rich_Mod(b,Base[cycle]);
cycle = pow(cycle,c);
cycle%=10;
printf("%d",cycle);
}
printf("\n");
}
}[/cpp]
And I have read the posts about 10515,
but I still can't figure out what's the problem with my code......
Could someone PLS help me ?
thanks a lot......
[cpp]#include <stdio.h>
#include <string.h>
#include <math.h>
int Rich_Mod(char *b,int cycle)
{
int t;
if(cycle==1)
return 1;
if(cycle==2)
return (b[strlen(b)1]'0')%2+2;
if(cycle==4)
{
if(strlen(b)>1)
t = 10*b[strlen(b)2]+b[strlen(b)1];
else
t = b[strlen(b)1];
return t%4+4;
}
}
void main()
{
char a[2000],b[2000];
int Base[10]={0,1,4,4,2,1,1,4,4,2};
int cycle,c;
int mode=0;
while(scanf("%s %s",&a,&b)==2)
{
if(strlen(a)==1 && a[0]=='0' && strlen(b)==1 && b[0]=='0')
break;
if(strlen(b)==1 && b[0]=='0')
printf("1");
else if(strlen(a)==1 && a[0]=='0')
printf("0");
else
{
cycle = a[strlen(a)1]'0';
c = Rich_Mod(b,Base[cycle]);
cycle = pow(cycle,c);
cycle%=10;
printf("%d",cycle);
}
printf("\n");
}
}[/cpp]
check this input
GET THE INPUTS FROM FILE & CHECK THE OUTPUT WITH YOUR OUTPUT
INPUT
INPUT
OUTPUT8 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
5 1
5 2
5 3
5 4
5 5
5 6
5 7
5 8
6 1
6 2
6 3
6 4
6 5
6 6
6 7
6 8
7 1
7 2
7 3
7 4
7 5
7 6
7 7
7 8
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
0 0
1
1
1
1
1
1
1
1
1
2
4
8
6
2
4
8
6
3
9
7
1
3
9
7
1
4
6
4
6
4
6
4
6
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
6
7
9
3
1
7
9
3
1
8
4
2
6
8
4
2
6
this time WA
what next...............?
what next...............?
RICH
welcome Rich!!!
actually i wasn't sure about your code. when i was taking input from file,it was showing some wrong. but those wrong output showing right when i was giving it manually.
that why i was confused.
but at last u got AC. that's a good news.
GOOD LUCK
actually i wasn't sure about your code. when i was taking input from file,it was showing some wrong. but those wrong output showing right when i was giving it manually.
that why i was confused.
but at last u got AC. that's a good news.
GOOD LUCK
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?Master wrote:Yes, I agree with seadoo.
one digit of m and two digits of n are enough.
M H Rasel
CUET Old Sailor

 Learning poster
 Posts: 82
 Joined: Thu Oct 10, 2002 1:15 pm
 Location: St. Johns, Canada
 Contact:
If a number N. If we can express N as
N = a*100 + b;
now if N is divisable by 4 then b must divisable by 4
and if not then b is not divisable by 4.
M H Rasel.
acmbeginner.tk
N = a*100 + b;
now if N is divisable by 4 then b must divisable by 4
and if not then b is not divisable by 4.
M H Rasel.
acmbeginner.tk