Potential of training number of Blue Bridge Cup algorithm Python 100 points

This question should ask for the maximum potential

Try to disassemble some numbers first ：

• 2 = 1 + 1, Then the factor is determined by 2 -> 1 * 1,2 Don't dismantle
• 3 In the same way, do not dismantle ,4 It can be disassembled into 2 + 2 The effect remains the same
• 5 = 2 + 3, Then the factor is determined by 5 -> 2 * 3, To dismantle
• 6 = 3 + 3 perhaps 2+ 2 + 2, Obviously, the first method is more profitable

The conclusion is , Remove as much as possible 3, Don't pull out 1. Give the timeout method first ：

time, res = divmod(num, 3)
if num == 1:
result = 1
# Input 1, Output 1
elif res == 2:
result = 3 ** time * 2
# Remainder is 2, Normal processing
elif res == 1:
result = 3 ** (time - 1) * 4
# Remainder is 1, Take out a 3 and 1 Merge into 4
else:
result = 3 ** time
# There is no remainder , Normal processing 

The reason for the timeout is that the data size is too large , So you have to do a power function by yourself

def quick_power(basic, time, mod=5218):
""" A fast power of two
mod: Mod """
result = 1
while time:
if time & 1:
result = result * basic % mod
basic = basic ** 2 % mod
time >>= 1
return result

Using bit operations to do bisection , Just push it with the draft paper

Python Built in ** Operator , Maybe it comes with a fast power of two , So if the function you made is in It is slower than the operator without remainder Of

  The final score 100, end