OJ Board

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.

yan4546 wrote:2 digits is not enough and 3 digits can do .

Nope, one digit of m and two digits of n are enough.

Yes, I agree with seadoo.
one digit of m and two digits of n are enough.

M H Rasel
CUET Old Sailor

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.

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 = dig-floor((double)dig/10)*10;

}
cout << dig << endl;

}
return 0;
}


[/cpp]

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

Problem Description :

Each line contains two integers m and n (Less than 10^101).

From your source code it looks like you are reading the input as integers. I don't think
int data type can handle such a large number

You must read the numbers as string and then process.

Hope it helps.

Here is the Input Description

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.

You are using integer variable for m and n, this is obviously wrong.

Oh, I misunderstood the question then

Thanks for help. I'll gonna fix that.

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]

GET THE INPUTS FROM FILE & CHECK THE OUTPUT WITH YOUR OUTPUT
INPUT

8 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

OUTPUT

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

^^...

thanks , I got accept.......

I have checked the input and the output,
but there is no problem (I mean the output is the same as yours...)


at the same time , I send my code again........

Unbelievably, I got accept ...

^^...

thanks for your help.....

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

Master wrote:Yes, I agree with seadoo.
one digit of m and two digits of n are enough.

M H Rasel
CUET Old Sailor

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?

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