PROBLEM LINK:
Setter : Mohammad Salik
Tester : Hasan Jaddouh
Editorialist : Mohammad Salik
Difficulty
Simple/EasyPrerequisites
Fast modular exponentiation, Observation skillsProblem
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 nonnegative single digit integer obtained by a process of summing digits,and on each iteration using the result from the previous iteration to compute a digit sum untill single digit number is reached.Explanation
For Subtask 1
We can simply find A^N as it doesn’t exceed 10^{15} and then evaluate F(A^N) by the recursive process mentioned in the definition of this function.Note that we can evaluate F(A^N) in less than 5 iterations.
For Subtask 2 and 3
Let us first observe the function $F$ first.What will be $F(X)$ for a single digit integer $X$ $?$ It will simply be the number itself.Or we can say for a single digit integer $X$ ,$F(X)=X\%9$ for $X!=9$ and $F(X)=9$ for $X=9$.Combining these two we can write $F(X)=X\%9 + 9*(X\%9==0)$ for a single digit integer $X$ where $X\%9==0$ will return $1$ only when $X$ is $9$. Now what will be $F(X)$ for a two digit integer $X$. For a two digit integer $X$ which is a multiple of $9$ observe that $F(X)=9$ and for $X$ not a multiple of $9$ , $F(X)= X\%9$. Generalising this we can define $F(X)$ as follows : $F(X)= X\%9 + 9*(X\%9==0)$ for any non negative integer $X$ where $(X\%9==0)$ will return $1$ only when $X$ is a multiple of $9$.Now lets try to find out F(X*X). Consider two Cases :

When X is a multiple of 9 i.e F(X)=9 then X*X is also a multiple of 9 and consequently F(X*X)=9. Also see here that F(F(X)*F(X))= F(9*9)=F(81)=9.Hence when X is a multiple of 9 then F(X*X)=F(F(X)*F(X)).

When X is not a multiple of 9 then F(X)=X\%9 . Hence, we have F(F(X)*F(X))=F((X\%9)*(X\%9))=((X\%9)*(X\%9))\%9 = (X*X)\%9 = F(X*X) .Hence in this case also F(X*X)=F(F(X)*F(X)).
So lets generalise this. F(X^2)=F(F(X)*F(X)). Similarly, F(X^4)=F( (F(F(X)*F(X)))^2 ).
Now for SUBTASK #2 where N<=100 we can evaluate F(A^N) by iterating from 1 to N and taking F at each step while multiplying.The following code evaluates this in N steps :
ll Res=1; for(int i=1;i<=N;i++) { Res=Res*A; Res=F(Res); }
For Subtask #3 we have N<=10^{18} and hence we cannot take N steps as it will timeout. we can write a function similar to a fast modular exponentiation to evaluate F(A^N) which evaluates this in logN steps.The following code evaluates this :
int solve(long long A,long long N) { long long res=1; while(N) { if(N%2==1) { res=res*F(A); res=F(res); } A=F(F(A)*F(A)); N/=2; } return res; }
The function F(A) for an integer A can be computed in O(1) easily as we have already defined this function.
Time Complexity
O(logN) per testcase
Space Complexity
O(1)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.