LeetCode 479 largest-palindrome-product

LeetCode 479

这个题目除了BruteForce的方法，我没有想出好的解法。最后求助于其他人的解法了，看到一个数学解法比较有意思，转成了python：

def largestPalindromeMath(self, n: int) -> int:
        '''假设确实存在 P = X * Y, X，Y都是接近10^n的数，那么
        记 X = 10^n - i, Y = 10^n - j, 并且我们知道: i*j < 10^n
        P = upper*10^n + lower = (10^n - i)*(10^n - j) = (10^n-i-j)*10^n + i*j
        那么: upper = 10^n-i-j, lower = i*j
        记 a = i + j, 就有 lower = i*(a-i), upper = 10^n-a
        所以我们可以遍历a来找整数i使得
        i^2 - a*i + lower = 0 => (i-a/2)^2 = 0.25*a^2 - lower
        a 从2开始, 检查 sqrt(a^2 - lower*4) 是否是整数, 如果是答案就是 upper*10^n + lower'''
        
        if n == 1: return 9
        a = 2
        while a < 10**n:
            upper = 10**n-a
            lower = int(str(upper)[::-1])
            if a**2-lower*4 >= 0 and (a**2-lower*4)**0.5 == int((a**2-lower*4)**0.5):
                return (upper*10**n+lower) % 1337
            a += 1