n度あることはn+1度ある

憶測が多いブログなので鵜呑みにしないこと

AGC028 A - Two Abbreviations

久しぶりに時間内(といってもペナルティ合わせて120分超え・・・)に300点問題をACできたので記念に書き込み。
まずLは必ずNMの最小公倍数です。自分で書いてみると分かりますが、STで被る文字(一致すべき文字)は必ず一致します。そのため最小公倍数でダメなときは、いくら大きな値をとってもよい文字列は存在しません。
配列Xよい文字列を生成するとして(実際にこれを行うとTLEします)、MよりNのほうが大きいと仮定します。
Tの文字を走査していき、そのとき文字被りをチェックする必要がある文字は、iがTの文字を参照している要素番号とすると、i*L/ML/Nの倍数のときです。
これ以外の文字は、Xに格納していくときに重複しないため、確認の必要がありません。
T[i]に対応する文字の場所はS[i*L/M/(L/N)]です。 T[i]X[i*L/M]に格納されます。L/NSの文字がXに格納される間隔です。そのためこの比で逆算的にT[i]と一致すべき文字のS[j]の位置を求めることができます。

#include <bits/stdc++.h>
using namespace std;
long Gcd(long m, long n){
    long temp;
    while (m % n != 0)
    {
        temp = n;
        n = m % n;
        m = temp;
    }
    return n;
}
int main(){
    long n,m;
    cin>>n>>m;
    string s,t;
    cin>>s>>t;
    long g = Gcd(n,m);
    g = (m*n)/g;
    if(m>n){
        swap(n,m);
        swap(s,t);
    }
    for(int i=0; i<m; i++){
        if((i*g/m)%(g/n)==0){
            if(t[i]!=s[i*g/m/(g/n)]){
                cout<<"-1";
                return 0;
            }
        }
    }
    cout<<g;
}