Help in ENCPH1

How to solve this problem:

PS: No editorial present for this

You need to understand is last three digits of n^k = last three digits of ((n-1)%1000 +1 )^k.

Hence u have to find
##(1^k)%1000 to (1000^k)%1000 And store it in an array of size 1000

And then after that add all of them(1^k to 1000^k)… And multiply it by floor(N/1000) and then add (N%1000) numbers from that array from starting (0th index) to it…

And print last three digits of it that is the answer…
#Note:- please use O(log(n)) approach with modulo for power function… inbuilt power function won’t work…

And make sure u don’t exceed long long int or int limit… (Do modulo with 1000)

For better understanding :-

Click to view

The reason for this soln is that… If u will see the last three digits of the series of 1^k , 2^k , … ,n^k.

Then you will notice that it repeats after 1000 numbers

i.e last three digits of.
1^k = 1001^k ,
2^k = 1002^k ,
3^k = 1003^k (only last three digits),…
So u can only calculated those first 1000 numbers and based on them further numbers could be obtained easily…

Thanks… :slight_smile:

Thanks man!

Welcome :slight_smile:

Advice :- Try to keep everything in long long as type casting problem would give wrong answers
PS:- my personal experience :smiley: