← 返回题目列表

AtCoder · xmascon19_h

H. 邮票 3

中文机器翻译题面 查看原题

配点 : 100 点

除了图章类型和约束之外,图章 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