Problem 350 「最小の最大と最大の最小による制約」

「サイズ n のリスト」とは, n 個の自然数を持つ数列のことである.
例えば (2,4,6), (2,6,4), (10,6,15,6), (11).

リストの最大公約数, gcdとは, リストのすべての数を割り切る最大の自然数を言う.
例 : gcd(2,6,4) = 2, gcd(10,6,15,6) = 1, gcd(11) = 11.

リストの最小公倍数, lcmとは, リストそれぞれの数で割り切ることができる最小の自然数を言う.
例 : lcm(2,6,4) = 12, lcm(10,6,15,6) = 30, lcm(11) = 11.

gcd ≥ G, lcm ≤ L となるサイズ N のリストの個数を f(G, L, N) としよう.
以下に例を示す:

f(10, 100, 1) = 91.
f(10, 100, 2) = 327.
f(10, 100, 3) = 1135.
f(10, 100, 1000) mod 1014 = 3286053.

f(106, 1012, 1018) mod 1014 を求めよ.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2023-02-04 (土) 10:36:35