非梅森素数

1999年，数学家首次发现了超过一百万位的素数$2^{6972593}−1$，这是一个梅森素数，共有2098960位。此后，更多形如$2^p−1$的梅森素数也被发现，其位数也越来越多。

另外，在2004年，数学家还发现了一个巨大的非梅森素数$28433\times 2^{7830457}+1$，共有2357207位。

求这个素数的最后十位数字。

本题难度:

解答

快速幂(将$a^k$的计算递归转化为$a^{k/2}$的计算)即得结果是$8739992577$。

m=10**10

def qp(k):
    if k < 10:
        return (1 << k)%m
    else:
        b=1 << (k/2)
        return (b*b*2)%m if k%2 else (b*b)%m

print (28433*qp(7830457)+1)%m