*[[Problem 552:https://projecteuler.net/problem=552]] 「連立合同式 2」 [#z0330500]

数列 A を次のように定める。

tex{A_{i}}; = (1 ≦ k ≦ i で tex{A_{i}}; mod tex{p_{i}}; = i となるような最小の自然数) とする。
&tex{A_{i}}; = (1 ≦ k ≦ i で &tex{A_{i}}; mod &tex{p_{i}}; = i となるような最小の自然数) とする。

例えば, tex{A_{2}}; = 5 である。 なぜなら,
例えば, &tex{A_{2}}; = 5 である。 なぜなら,

   tex{A_{2}}; mod 2 = 1
   tex{A_{2}}; mod 3 = 2
   &tex{A_{2}}; mod 2 = 1
   &tex{A_{2}}; mod 3 = 2

を満たし, かつこれが最小だからである。

また, tex{A_{3}}; = 23 である。 なぜなら,
また, &tex{A_{3}}; = 23 である。 なぜなら,

   tex{A_{3}}; mod 2 = 1
   tex{A_{3}}; mod 3 = 2
   tex{A_{3}}; mod 5 = 3
   &tex{A_{3}}; mod 2 = 1
   &tex{A_{3}}; mod 3 = 2
   &tex{A_{3}}; mod 5 = 3

を満たし, かつこれが最小だからである。

また, tex{A_{4}}; = 53, tex{A_{5}}; = 1523 である。また, tex{A_{10}}; = 5765999453 である。
また, &tex{A_{4}}; = 53, &tex{A_{5}}; = 1523 である。また, &tex{A_{10}}; = 5765999453 である。

そこで, S(n) = (1 ≦ i ≦ n (i は素数) で 数列 A の中に i で割り切れるものが1つ以上あるような整数 i の個数) とする。
例えば, S(50) = 5 + 23 + 41 = 69 です。 なぜなら, 5 は tex{A_{2}}; = 5 を割ることができ, 23 は tex{A_{3}}; = 23 を割ることができ, 41 は tex{A_{10}}; = 5765999453 を割ることができるからである。
例えば, S(50) = 5 + 23 + 41 = 69 です。 なぜなら, 5 は &tex{A_{2}}; = 5 を割ることができ, 23 は &tex{A_{3}}; = 23 を割ることができ, 41 は &tex{A_{10}}; = 5765999453 を割ることができるからである。
また, 50以下の5, 23, 41ではない他の12個の素数は, Aに入っているいずれの整数も割ることができない。

そのとき, S(300000) を求めなさい。

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS