ABX01 - EDITORIAL

This is my solution.

I did it in a different way.
I took the sum of digits according to the question given in a query. And then found out the pattern in which result is repeating.
Finally, printed the result according to the condition satisfied by the exponential term given in the query.

Here is my solution.

2 Likes

DONE THIS USING OBSERVATION CodeChef: Practical coding for everyone

And here is O(1) solution.

1 Like

@abx_2109 u can do this question more efficiently when each time for updating res u should go for checking

if(res%9==0) res=9;else res%=9;

rather than again making an recursive function as given in definition

And similarly updating A with

     A = ((A%M)*(A%M))%M;
      
    if(A%9==0) A=9;else A%=9;

Problem Link
Contest
Practise

Setter : Mohammad Salik

Tester : Hasan Jaddouh

Editorialist : Ashwany Aggarwal

Difficulty:
Easy

Prerequisites:
Mathematics,Observation skills

Problem
You are given two integers A and N. The task is to compute F(A^N) where F(X) is a function which results in a non-negative single digit integer obtained by a process of summing digitsuntil single digit number is reached.

Explanation:

STEP 1: First of all we find the sum of integers of the given integer A until it reaches to a single integer (say y), using function :

int digsum(unsigned long long p)
{ unsigned long long x,sum=0;
     while(p>0)
               {
                 while(p != 0)
                 {
                      x = p%10;
                      sum = sum+x;
                      p=p/10;
                 }
                 if(sum > 9)
                 {
                         p = sum;
                        sum = 0;
                 }
               }
               return sum;
}

Now, by the property of exponents that sum of digits repeat after every 6th exponent.i.e, digsum(A^N)= digsum(A^(N%6)), (except for A=3 or A=6 , where A^N= A for N=1 and A^N=9 for N>1).

For eg. 2^1=2, 2^7=128=1+2+8=11=1+1=2

For eg: 3^1=3; 3^4=81=8+1=9, 6^3=216=2+1+6=9 (you can check for any N).

STEP 2:

Now we have y (the single digit sum for A). Now We have 2 cases either y=(3 or 6) or y= else than 3 or 6.

1st case: If y= 3 or 6 or 9

1: If N>1 output 9

2: If N=1 output Y

2nd case: Y is not 3 or 6 or 9.(I have taken 9 also because for 9 answer is always 9)

Then take remainder of the given large N when divided by 6 (say z).(The main LOGIC)
Now single digit raised to power maximum 5 will be 3 digit in worst case this reduces the complexity of problem.

Step 3:
Find y^z and apply the same function. You will get the required answer.

Here is my solution: https://www.codechef.com/viewsolution/16728889

1 Like

As some wonder why there is a magic modulo 9, here is a short explanation:

Any number can be written as a sum of power of 10 and you can write it like this:

1543 = 1 * (999+1) + 5 * (99+1) + 4 * (9+1) + 3

If you rearrange:

1543 = (1 * 999 + 5 * 99 + 4 * 9) + (1 + 5 + 4 + 3)

And then you understand why mod 9 is the magic trick.

More details here: A neat number trick: digital roots and modulo-9 arithmetic | Flying Colours Maths

9 Likes

We can use "set stl " also

I was trying to use recursive version of fast exponentiation algorithm but getting TLE on 2nd and 3rd subtask. Can anyone help me regarding same? Please upvote this answer so that I can ask queries :slight_smile:

https://www.codechef.com/viewsolution/16740009

1 Like

Superfast - 0s

And it works with arbitrarily large integers!

@eugalt u really squeezed up !!!

1 Like

Are you sure it’s O(1)? :wink:

3 Likes

Consider this TC:

2

18 0

18 1

Expected o/p:

1

9

Your code gives:

18

18

Hope this helps!

For A=18, N=0 and A=18, N=1 your code gives 9 and 0 respectively which should be 1 and 9.

1 Like

i got the mistake. cout<<y<<endl; instead of cout<<a<<endl;. BTW i have not considered n=0 as per constrained.
Thanks a lot.

after reading the comment of @pk301 i realized that it is O(no of digits) i didn’t do a proper analysis sorry saw you solution it is actually O(1) well done

well done @eugalt if any one didn’t get % 9 part the can look the comment of @sideralis nice explanation both of you @eugalt your code is very well represented.

thanks a lot @ayan_nitd for second test case. I found the mistake(18,0 is not a valid testcase)

O(no of digits) is O(log N).

Why my code is giving WA. I solved using digital root
https://www.codechef.com/viewsolution/36157204