CF356B.Xenia and Hamming

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Xenia is an amateur programmer. Today on the IT lesson she learned about the Hamming distance.

The Hamming distance between two strings s=s1s2... sns=s_{1}s_{2}...\ s_{n} and t=t1t2... tnt=t_{1}t_{2}...\ t_{n} of equal length nn is value . Record [siti][s_{i}≠t_{i}] is the Iverson notation and represents the following: if sitis_{i}≠t_{i} , it is one, otherwise — zero.

Now Xenia wants to calculate the Hamming distance between two long strings aa and bb . The first string aa is the concatenation of nn copies of string xx , that is, . The second string bb is the concatenation of mm copies of string yy .

Help Xenia, calculate the required Hamming distance, given n,x,m,yn,x,m,y .

输入格式

The first line contains two integers nn and mm (1<=n,m<=1012)(1<=n,m<=10^{12}) . The second line contains a non-empty string xx . The third line contains a non-empty string yy . Both strings consist of at most 10610^{6} lowercase English letters.

It is guaranteed that strings aa and bb that you obtain from the input have the same length.

输出格式

Print a single integer — the required Hamming distance.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输入输出样例

  • 输入#1

    100 10
    a
    aaaaaaaaaa
    

    输出#1

    0
    
  • 输入#2

    1 1
    abacaba
    abzczzz
    

    输出#2

    4
    
  • 输入#3

    2 3
    rzr
    az
    

    输出#3

    5
    

说明/提示

In the first test case string aa is the same as string bb and equals 100 letters a. As both strings are equal, the Hamming distance between them is zero.

In the second test case strings aa and bb differ in their 3-rd, 5-th, 6-th and 7-th characters. Thus, the Hamming distance equals 4.

In the third test case string aa is rzrrzr and string bb is azazaz. The strings differ in all characters apart for the second one, the Hamming distance between them equals 5.

首页