Problem 537 「タプルの数え上げ」

素数計数関数, すなわち x 以下の素数の個数を π(x) としよう.
例えば, π(1)=0, π(2)=1, π(100)=25.

下記の条件を満たす k-タプル (x&sub{1};,…,x&sub{k};) の個数を T(n,k) としよう:

  1. すべての x&sub{i}; が正整数である.
  2. &ref(): File not found: "p537_eq.png" at page "Problem 537";

例えば T(3,3)=19.
その19個のタプルとは, (1,1,5), (1,5,1), (5,1,1), (1,1,6), (1,6,1), (6,1,1), (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1), (1,2,4), (1,4,2), (2,1,4), (2,4,1), (4,1,2), (4,2,1), (2,2,2).

T(10,10) = 869 985, T(10&sup{3};,10&sup{3};) ≡ 578 270 566 (mod 1 004 535 809) が与えられている.

T(20 000, 20 000) mod 1 004 535 809 を求めよ.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2015-12-06 (日) 07:23:55