$S_i$ を次の擬似乱数生成器が生成する整数列とする。

• $S_0 = 290797$

• $S_{i+1} = {S_i} ^2 \bmod 50515093$

$M(n)$ を $0 \le i \lt j \lt n$ についての2つ組の積 $S_i S_j$ の中央値とする。 $M(3) = 3878983057768$ , $M(103) = 492700616748525$ である。

$M(1\,000\,003)$ を求めよ。

正整数 $n$ に対して、関数 $g(n)$ を次のように定義する：

例えば $g(4) = -\gcd(4,1^2) + \gcd(4,2^2) - \gcd(4,3^2) + \gcd(4,4^2) = -1+4-1+4=6$ となる。また、$g(1234)=1233$ が与えられている。

$\displaystyle G(N) = \sum_{n=1}^N g(n)$ としよう。$G(1234) = 2194708$ が与えられている。

$G(12345678)$ を求めよ。

(原題 Hybrid Integers)

相異なる2つの素数 $p, q$ により $p^q q^p$ と表せる整数をハイブリッド整数と呼ぶ。 例えば、$800 = 2^5 5^2$ はハイブリッド整数である。

$C(n)$を、$n$以下のハイブリッド整数の個数と定義する。 $C(800) = 2, C(800^{800}) = 10790$ である。

$C(800800^{800800})$ を求めよ。