鱼C论坛

 找回密码
 立即注册
查看: 6370|回复: 2

题目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)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。
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2016-11-29 22:48:29 | 显示全部楼层
不知道有没有不用暴力求解的方法,算法是挺简单的,但是很耗时。
  1. #coding:utf-8
  2. plist = []
  3. primes = [True] * 1000000
  4. primes[0], primes[1] = False, False
  5. for i, prime in enumerate(primes):
  6.     if prime:
  7.         for j in range(i * i, 1000000, i):
  8.             primes[j] = False
  9. for i, prime in enumerate(primes):
  10.     if prime:
  11.         plist.append(i)
  12. def psr(n):
  13.     pn = plist[n-1]
  14.     return ((pn-1)**n + (pn+1)**n) % (pn*pn)

  15. for i in range(3,200000):
  16.     if psr(i) > 10**10:
  17.         print (i)
  18.         break
复制代码

输出:
21035
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-12-1 06:21:36 | 显示全部楼层
  1. .bss
  2. PL:
  3.      .zero 200000

  4. .text


  5. main:
  6. push 200000
  7. xor ecx,ecx
  8. inc ecx
  9. mov ebx,ecx
  10. inc ecx
  11. mov edi,ecx

  12. _d:
  13. cmp BYTE PTR PL[ebx],0
  14. jnz _n
  15. cmp ebx,315
  16. jnc _f
  17. mov eax,ebx
  18. mul edi
  19. inc eax
  20. mov esi,eax
  21. inc eax
  22. mul ebx
  23. _l:
  24. inc BYTE PTR PL[eax]
  25. add eax,esi
  26. cmp eax,[esp]
  27. jc _l
  28. inc ecx
  29. _n:
  30. inc ebx
  31. jmp _d

  32. _f:
  33. xor edx,edx
  34. push 100000
  35. _a:
  36. inc ecx
  37. _i:
  38. inc ebx
  39. cmp BYTE PTR PL[ebx],0
  40. jnz _i
  41. test cl,1
  42. jz _a
  43. cmp ebx,[esp]
  44. jc _a
  45. push 705032704
  46. mov eax,ebx
  47. mul edi
  48. inc eax
  49. mul ecx
  50. test edx,edx
  51. jz _b
  52. dec edx
  53. jnz _ok
  54. cmp eax,[esp]
  55. jc _b
  56. jmp _ok

  57. _b:
  58. inc ecx
  59. _j:
  60. inc ebx
  61. cmp BYTE PTR PL[ebx],0
  62. jnz _j
  63. test cl,1
  64. jz _b
  65. mov eax,ebx
  66. mul edi
  67. inc eax
  68. mul ecx
  69. test edx,edx
  70. jz _b
  71. dec edx
  72. jnz _ok
  73. cmp eax,[esp]
  74. jc _b
  75. jmp _ok

  76. _ok:
  77. add esp,12
复制代码


所用时间: 0.0011秒
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-4-26 18:21

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表