PROBLEM LINK:
Setter : Mohammad Salik
Tester : Hasan Jaddouh
Editorialist : Mohammad Salik
Difficulty
Simple/Easy
Prerequisites
Fast modular exponentiation, 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 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.
