← 返回题目列表

Codeforces · 356/B

B. 齐妮亚和汉明

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

Xenia 是一位业余程序员。今天在 IT 课上她学到了汉明距离。

长度相等的两个字符串 s = s1s2... sn 和 t = t1t2... tn 之间的汉明距离值为 $$\sum_{i=1}^{n}[s_i \neq t_i]$$。记录 [si ≠ ti] 是艾弗森符号,表示如下:如果 si ≠ ti,则为 1,否则为 0。

现在 Xenia 想要计算两个长字符串 a 和 b 之间的汉明距离。第一个字符串 a 是字符串 x 的 n 个副本的串联,即 $$a = x + x + \cdots + x = \sum_{i=1}^{n} x$$。第二个字符串 b 是字符串 y 的 m 个副本的串联。

帮助 Xenia,计算所需的汉明距离,给定 n、x、m、y。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 1012)。第二行包含一个非空字符串 x。第三行包含一个非空字符串 y。这两个字符串最多由 106 个小写英文字母组成。

保证从输入中获得的字符串 a 和 b 具有相同的长度。

输出

打印一个整数 - 所需的汉明距离。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

100 10
a
aaaaaaaaaa

输出 #1

0

输入 #2

1 1
abacaba
abzczzz

输出 #2

4

输入 #3

2 3
rzr
az

输出 #3

5

注意

在第一个测试用例中,字符串 a 与字符串 b 相同,并且等于 100 个字母 a。由于两个字符串相等,因此它们之间的汉明距离为零。

在第二个测试用例中,字符串 a 和 b 的第 3 个、第 5 个、第 6 个和第 7 个字符不同。因此,汉明距离等于 4。

在第三个测试用例中,字符串 a 是 rzrrzr,字符串 b 是 azazaz。除了第二个字符串之外,字符串的所有字符都不同,它们之间的汉明距离等于 5。