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