六省联考2017 問題の解法
P3745 [六省聯考 2017] 期末試験
m 種の試験があり、各試験 i は第 b_i 日に成績が発表される予定である。n 人の学生が成績を待っている。学生 i は第 t_i 日までにすべての成績を知りたいと思っている。最終的に最も遅く成績が出る試験の日を T とする。以下の3種類の不快度が生じる。
各学生は C × max(T - t_i, 0) の不快度を負担する。
試験 x を1日遅らせて試験 y ...
10月6日 06:50 投稿
線形ふるい法による素数、オイラー関数、メビウス関数の高速計算
線形ふるい法 (Linear Sieve)
線形ふるい法は、ある範囲内の素数を効率的に求めるアルゴリズムです。このアルゴリズムの時間計算量はO(n)であり、各合成数が一度だけふるい落とされることを保証します。本稿では、線形ふるい法を用いて素数、オイラー関数、メビウス関数を計算する方法を解説します。
1. 素数の線形ふるい
素数の線形ふるいは、指定された上限Nまでのすべ ...
5月18日 22:09 投稿