ABX01 - EDITORIAL

editorial
, , , , ,
2

i have done this question in O(1)
link:-CodeChef: Practical coding for everyone

2 Likes
3

When you realize that F(A)\equiv A \mod 9 all you need to do is compute A^N \mod 9.

Solution.

And that’s also what the tester’s solution does.

6 Likes
4

Can anyone tell me the mistake in this solution? It passed for the last test case but failed in the first two.
I am not getting the mistake.

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

5

My this code is passing for 70 pts and getting WA for first two subtasks. I don’t know why it is happening atleast in first subtask because i have matched my output of all the possible test cases for first subtask with ouput of an AC code. If anyone could please help. @abx_2109

6

I have solved this in O(no_of_digits_in_N) but not sure whether my approach is fully correct or not. I have observed that after certain number of steps there will be a cycle and thus i just sum the digits of N untill it becomes single digit and then just print the answer for that single digit for that power.

my solution : CodeChef: Practical coding for everyone

I don’t know whether it fully correct or not and if it is and someone has some mathematical stuff regarding it’s proof then please share :slight_smile:

7

This is my solution.

8

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
9

DONE THIS USING OBSERVATION CodeChef: Practical coding for everyone

10

And here is O(1) solution.

1 Like
11

@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;
12

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
13

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
14

We can use "set stl " also

15

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
16

Superfast - 0s

And it works with arbitrarily large integers!

17

@eugalt u really squeezed up !!!

1 Like
18

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

3 Likes
19

Consider this TC:

2

18 0

18 1

Expected o/p:

1

9

Your code gives:

18

18

Hope this helps!

20

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
21

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.