You are not logged in. Please login at www.codechef.com to post your questions!

×

Spoj - Last Digit - RE

I know that modular exponentiation is enough to solve this problem but I came across a formula on Quora by Divanshu Garg ( http://qr.ae/R753zZ ). Using his formula the problem simply boils down to calculate and print pow(a%10,b%4)%10 but this approach is giving me Runtime error. Here is my code. http://ideone.com/Y5VQLJ Problem link : http://www.spoj.com/problems/LASTDIG/ Thanks for reading! :)

asked 17 Jul '15, 03:19

h1ashdr%40gon's gravatar image

3★h1ashdr@gon
2912319
accept rate: 10%

edited 17 Jul '15, 03:19


include <stdio.h>

include <math.h>

int main()

{

    int t,a,b,res;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&a,&b);

        if (b==0)

            printf("1\n");

        else

        {

            b=b%4;

            res=pow(a,b);

            if(b==0)

                res=pow(a,4);

            printf("%d\n",res%10);

        }

    }

    return 0;

}

Try this code, as you said, a%10, it will contain 1 digit only and b%4, it will also contain one digit only. So, you can use pow() function only.

I think the problem is with your modexpo() function. It gives runtime error because of the bitwise operator used. I changed b>>=1 to b/=2 and it gave Wrong answer on spoj but not Runtime error. So, change your modexpo() function. I better suggest you to use the code given above.

link

answered 17 Jul '15, 04:01

likecs's gravatar image

6★likecs
3.7k2279
accept rate: 9%

Simply pow(a%10,b%4) gives WA. Tried a simple implementation here, http://ideone.com/jpkR2K

(17 Jul '15, 11:45) h1ashdr@gon3★

@h1ashdr@gon... i think you have not yet understood the concept (as mentioned by you on quora) well. For example let a = 2 and b=4, then ans is last digit of 2^4=16 i.e 6. But your code prints out 1 which is why it is WA. Understand that the answer for any a repeats after a max of 4 iterations. For eg for a=3 it repeats as 3, 9, 7 and 1 while for a=6, it repeats as 6,6,6,6 so after taking b%4 which gives answer in the range [0,3] doesn't actually give the correct answer when b is a multiple of 4. So, as i wrote my code above consider the code which checks explicitly for the case when b%4=0, just add this condition and i think your code will run fine now...

Happy coding.

link

answered 18 Jul '15, 08:15

likecs's gravatar image

6★likecs
3.7k2279
accept rate: 9%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,114
×13
×9

question asked: 17 Jul '15, 03:19

question was seen: 1,161 times

last updated: 18 Jul '15, 08:15