784. Reciprocal Pairs

Let's call a pair of positive integers $p$$p$, $q$$q$ ($p<q$$p \lt q$) reciprocal, if there is a positive integer $r<p$$r\lt p$ such that $r$$r$ equals both the inverse of $p$$p$ modulo $q$$q$ and the inverse of $q$$q$ modulo $p$$p$.

For example, $(3,5)$$(3,5)$ is one reciprocal pair for $r=2$$r=2$. Let $F(N)$$F(N)$ be the total sum of $p+q$$p+q$ for all reciprocal pairs $(p,q)$$(p,q)$ where $p\le N$$p \le N$.

$F(5)=59$$F(5)=59$ due to these four reciprocal pairs $(3,5)$$(3,5)$, $(4,11)$$(4,11)$, $(5,7)$$(5,7)$ and $(5,19)$$(5,19)$. You are also given $F({10}^2)=697317$$F(10^2) = 697317$.

Find $F(2\cdot {10}^6)$$F(2\cdot 10^6)$.

784. 互反数对

我们称数对 $(p,q)(p<q$$(p, q) (p \lt q$) 为互反数对，当且仅当存在一个正整数 $r<p$$r < p$，使得 $r$$r$ 既为模 $q$$q$ 意义下 $p$$p$ 的乘法逆，也为模 $p$$p$ 意义下 $q$$q$ 的乘法逆。例如 $(3,5)$$(3,5)$ 是一对互反数对，令 $r=2$$r=2$ 即可。

记 $F(N)$$F(N)$ 为所有满足 $p\le N$$p \le N$ 的互反数对 $(p,q)$$(p,q)$ 的 $p+q$$p+q$ 之和。例如 $F(5)=59$$F(5)=59$，因为共有 $(3,5)$$(3,5)$、$(4,11)$$(4,11)$、$(5,7)$$(5,7)$ 和 $(5,19)$$(5,19)$ 四个满足条件的互反数对。已知：$F({10}^2)=697317$$F(10^2) = 697317$。

求 $F(2\cdot {10}^6)$$F(2\cdot 10^6)$。

点 这个链接 回到源站。

点 这个链接 回到详细版题目目录。