結果

問題 No.1544 [Cherry 2nd Tune C] Synchroscope
コンテスト
ユーザー homer12
提出日時 2021-06-11 23:06:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,037 bytes
コンパイル時間 3,516 ms
コンパイル使用メモリ 210,020 KB
最終ジャッジ日時 2025-01-22 06:52:44
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 39 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using iPair = pair<int,int>;
using lPair = pair<ll, ll>;
using ivector = vector<int>;
using lvector = vector<ll>;
using istack = stack<int>;
using iqueue = queue<int>;
using ivv = vector<vector<int>>;
using lvv = vector<vector<ll>>;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
vector<iPair> dir = {{1,0}, {-1,0}, {0,1}, {0,-1}};
#define dump(x) cout << #x << " = " << (x) << endl
#define ALL(x) begin(x),end(x)
#define rep(i,s,e) for(ll i=(s), i_stop=(e); i<i_stop; ++i)
#define repRev(i,s,e) for(ll i=(e)-1, i_stop=(s); i>=i_stop; --i)
#define range(i,s,n) for(ll i=(s), i_stop=(s)+(n); i<i_stop; ++i)
#define rangeRev(i,s,n) for(ll i=(s), i_stop=(s)-(n); i>i_stop; --i)
#define foreach(x,container) for(auto &&x:container)
template<typename T> bool chmax(T& a, const T b) {if(a<b) {a=b;return true;} return false;}
template<typename T> bool chmin(T& a, const T b) {if(a>b) {a=b;return true;} return false;}
template<typename T> void printArr(vector<T> &arr){
    for(auto &x:arr) {cout << x << " ";} cout << endl;
}

/*
因爲涉及到餘數，寫代碼從0開始。
*/

struct NumberTheory{
    inline ll mod(ll a, ll m){
        return (a % m + m) % m;
    }
 
    // 參數引用形式返回 ap + bq = gcd(a,b) 的一組解(p0, q0)
    // 返回值形式返回 gcd(a,b)
    ll extGcd(ll a, ll b, ll &p, ll &q){
        if( b == 0 ) { p = 1; q = 0; return a; }
        ll d = extGcd(b, a%b, q, p);
        q = q - (a/b) * p;
        return d;
    }

    // 當a與m互素時，返回乘法逆元。否則返回-1
    ll modinv(ll a, ll m) {
        ll p, q;
        ll d = extGcd(a,m,p,q);
        return (d==1)?mod(p,m):-1;
    }


    // 返回中國剩餘定理的解以及最小公倍數
    pair<ll,ll> crt(vector<ll> b, vector<ll> m){
        ll r = 0, M = 1;
        for(int i = 0; i < (int)b.size(); ++i){
            ll p, q;
            ll d = extGcd(M, m[i], p, q);
            if((b[i] - r) % d != 0) return make_pair(0, -1);
            ll tmp = (b[i] - r) / d * p % (m[i] / d);
            r += M * tmp;
            M *= m[i] / d;
        }
        return make_pair(mod(r, M), M);
    }
};


void solve() {
    int n,m; cin>>n>>m;

    
    map<int,int> mapping;
    vector<iPair> res;
    ivector a(n); range(i, 0, n) {cin>>a[i]; mapping[a[i]] = i;}
    ivector b(m); range(i, 0, m) {
        cin>>b[i];
        if(mapping.count(b[i])) {
            res.emplace_back(mapping[b[i]], i);
        }
    }

    if(res.size() == 0) {
        cout<<-1<<endl; return;
    }

    NumberTheory nt;
    ll ans = LINF;
    for(auto [i,j] : res) {
        // n,m不互素的話不一定有解
        ll p,q;
        ll g = nt.extGcd(i,j,p,q);
        if(i%g != j%g) continue;
        lvector mod = {(ll)n, (ll)m};
        lvector b = {(ll)i, (ll)j};
        auto [t, M] = nt.crt(b, mod);
        chmin(ans, t);
    }

    cout << ans+1 << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}
0