题目123：考察(Pn-1)^n+(Pn+1)^n除以Pn^2的余数
Prime square remaindersLet pn be the nth prime: 2, 3, 5, 7, 11, ..., and let r be the remainder when (pn−1)n + (pn+1)n is divided by pn2.
For example, when n = 3, p3 = 5, and 43 + 63 = 280 ≡ 5 mod 25.
The least value of n for which the remainder first exceeds 109 is 7037.
Find the least value of n for which the remainder first exceeds 1010.
题目：
令 pn 为第 n 个素数：2,3,5,7,11……，令 r 为 (pn−1)n + (pn+1)n 除以 pn2 的余数。
例如，当 n = 3，p3 = 5时，43 + 63 = 280 ≡ 5 mod 25.
使得余数超过 109 的 n 的最小值是 7037。
求使得余数超过超过 1010 的最小的 n。 不知道有没有不用暴力求解的方法，算法是挺简单的，但是很耗时。
#coding:utf-8
plist = []
primes = * 1000000
primes, primes = False, False
for i, prime in enumerate(primes):
if prime:
for j in range(i * i, 1000000, i):
primes = False
for i, prime in enumerate(primes):
if prime:
plist.append(i)
def psr(n):
pn = plist
return ((pn-1)**n + (pn+1)**n) % (pn*pn)
for i in range(3,200000):
if psr(i) > 10**10:
print (i)
break
输出：
21035 .bss
PL:
.zero 200000
.text
main:
push 200000
xor ecx,ecx
inc ecx
mov ebx,ecx
inc ecx
mov edi,ecx
_d:
cmp BYTE PTR PL,0
jnz _n
cmp ebx,315
jnc _f
mov eax,ebx
mul edi
inc eax
mov esi,eax
inc eax
mul ebx
_l:
inc BYTE PTR PL
add eax,esi
cmp eax,
jc _l
inc ecx
_n:
inc ebx
jmp _d
_f:
xor edx,edx
push 100000
_a:
inc ecx
_i:
inc ebx
cmp BYTE PTR PL,0
jnz _i
test cl,1
jz _a
cmp ebx,
jc _a
push 705032704
mov eax,ebx
mul edi
inc eax
mul ecx
test edx,edx
jz _b
dec edx
jnz _ok
cmp eax,
jc _b
jmp _ok
_b:
inc ecx
_j:
inc ebx
cmp BYTE PTR PL,0
jnz _j
test cl,1
jz _b
mov eax,ebx
mul edi
inc eax
mul ecx
test edx,edx
jz _b
dec edx
jnz _ok
cmp eax,
jc _b
jmp _ok
_ok:
add esp,12
所用时间: 0.0011秒
页:
[1]