蟻本の練習問題埋め2-6(2)

素数

AOJ 0009 - Prime Number

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0009
やるだけ

POJ 3126 - Prime Path

http://poj.org/problem?id=3126
グラフ作ってダイクストラするだけ

POJ 3421 - X-factor Chains

http://poj.org/problem?id=3421

問題

Xが与えられる。
1 = X0, X1, X2, …, Xm = X
ただし、
Xi < Xi+1 かつ Xi は Xi+1 を割り切る
という制約を満たす列Xiのうち、最長なものの長さと、その長さを達成する列の個数を求めよ。

制約

X<=2^20

解法

Xiとして考えられるのはXの約数。
Xを素因数分解する。
最長の列は素因数を1個ずつ掛けていくもの。
すなわち最長なものの長さは、素因数の数。
個数は、素因数を1列に並べる並べ方なので、例えば素因数分解の結果が
a^p * b^q
ならば、
(p+q)! / (p! * q!)
になる。
20!はlong longに入るので、普通に計算すれば良い。（OUPCの反省）

POJ 3292 - Semi-prime H-numbers

http://poj.org/problem?id=3292

問題

4n+1で表される正の数をH-numberと呼ぶ。
1*h以外にH-numberの積で表現出来無いhをH-primeと呼ぶ。
H-primeとH-primeの積で表現できるものをH-semi-primeと呼ぶ。
nが与えられるので、n以下のH-semi-primeの数を求めよ。

制約

n<=10^6+1

解法

10^6+1以下のH-primeをエラトステネスの篩っぽく列挙する。
H-primeの積を10^6+1以下の範囲で全部計算し、テーブルの対応する箇所にフラグを立てる。
あとは累積和。