H - Stamps 3 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

Stamps 1 ~ 4 において，スタンプの種類と制約以外の問題設定は共通しています．

問題文

うさぎは H \times W の長方形のマス目を持っている． マス目の上から i 行目 (1 \le i \le H)，左から j 列目 (1 \le j \le W) のマスをマス (i,j) と呼ぶ．

マス (i,j) の初期状態は文字 S_{i,j} で表され，# は黒く塗られていること，. は塗られていないことを意味する．

うさぎはクリスマスプレゼントとしてスタンプセットをもらった．

このスタンプセットには 10^{10} 種類のスタンプが入っており，スタンプ k\ (1 \le k \le 10^{10}) は，p_k マスおきに横一列に並んだマスの集合を一度に黒く塗ることができる． ただし，ここで p_k は k 番目に小さい奇素数とする． すなわち，スタンプ k を 1 回押すと，整数 i,j_0 を選んだとき，j = j_0+a*p_k となる整数 a が存在するようなマス (i,j) を全て黒く塗ることができる．

うさぎはこのスタンプセットを使って全てのマスを黒く塗ろうとしている． 最小で何回スタンプを押せば良いだろうか？

制約

  • 1 \le H,W
  • H*W \le 10^5
  • S_{i,j} は . または #

入力

入力は以下の形式で標準入力から与えられる．

H W
S_{1,1}S_{1,2}...S_{1,W}
S_{2,1}S_{2,2}...S_{2,W}
:
S_{H,1}S_{H,2}...S_{H,W}

出力

全てのマスが黒く塗られた状態にするためにスタンプを押す必要のある回数の最小値を出力せよ．

入力例 1

2 15
.#.##.##.#..##.
########.#.####

出力例 1

4

例えば以下のように押せばよい． 2 は奇素数でない点に注意せよ．

  • スタンプ 1 (p_1 = 3) を i = 1, j_0 = 3 として押す．
  • スタンプ 2 (p_2 = 5) を i = 1, j_0 = 1 として押す．
  • スタンプ 4 (p_4 = 11) を i = 2, j_0 = 0 として押す．
  • スタンプ 4 (p_4 = 11) を i = 2, j_0 = -2 として押す．

入力例 2

5 1
.
.
#
.
.

出力例 2

4

入力例 3

20 19
#.#.##..#.###.#.#.#
.#.###..#.##.##.##.
#.##..#.##..#..#..#
######.######.####.
.#########.####.###
..###.##..#####.##.
#########.#########
.##.##.#####.##.###
##.#####.#####.##.#
.##.#..##.##.###.##
#.##.##.#..##..#.##
#.##.###.##########
#.######..####.####
.##.##.##..#.##.##.
########.##########
##.########.##.#..#
#.##.##.#####.##.##
#############..####
..#.##..##..#..#.#.
.##.#..#####.##.##.

出力例 3

37