题目123：考察(Pn-1)^n+(Pn+1)^n除以Pn^2的余数

欧拉计划 · 发表于 2016-8-23 16:31:27

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

Prime square remainders

Let pn be the nth prime: 2, 3, 5, 7, 11, ..., and let r be the remainder when (pn−1)ⁿ + (pn+1)ⁿ is divided by pn².

For example, when n = 3, p3 = 5, and 4³ + 6³ = 280 ≡ 5 mod 25.

The least value of n for which the remainder first exceeds 10⁹ is 7037.

Find the least value of n for which the remainder first exceeds 10¹⁰.

题目：

令 pn 为第 n 个素数：2,3,5,7,11……，令 r 为 (pn−1)ⁿ + (pn+1)ⁿ 除以 pn² 的余数。

例如，当 n = 3，p3 = 5时，4³+ 6³ = 280 ≡ 5 mod 25.

使得余数超过 10⁹ 的 n 的最小值是 7037。

求使得余数超过超过 10¹⁰ 的最小的 n。

jerryxjr1220 · 发表于 2016-11-29 22:48:29

不知道有没有不用暴力求解的方法，算法是挺简单的，但是很耗时。

#coding:utf-8
plist = []
primes = [True] * 1000000
primes[0], primes[1] = False, False
for i, prime in enumerate(primes):
    if prime:
        for j in range(i * i, 1000000, i):
            primes[j] = False
for i, prime in enumerate(primes):
    if prime:
        plist.append(i)
def psr(n):
    pn = plist[n-1]
    return ((pn-1)**n + (pn+1)**n) % (pn*pn)

for i in range(3,200000):
    if psr(i) > 10**10:
        print (i)
        break

输出：
21035

fc1735 · 发表于 2016-12-1 06:21:36

.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[ebx],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[eax]
add eax,esi
cmp eax,[esp]
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[ebx],0 
jnz _i
test cl,1
jz _a
cmp ebx,[esp]
jc _a
push 705032704
mov eax,ebx
mul edi
inc eax
mul ecx
test edx,edx
jz _b
dec edx
jnz _ok
cmp eax,[esp]
jc _b
jmp _ok

_b:
inc ecx
_j:
inc ebx
cmp BYTE PTR PL[ebx],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,[esp]
jc _b
jmp _ok

_ok:
add esp,12

所用时间: 0.0011秒

账号		自动登录	找回密码
密码			立即注册