結果

問題 No.896 友達以上恋人未満
ユーザー QCFium
提出日時 2019-09-27 22:22:55
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,405 ms / 3,500 ms
コード長 1,746 bytes
コンパイル時間 1,831 ms
コンパイル使用メモリ 175,336 KB
実行使用メモリ 144,852 KB
最終ジャッジ日時 2024-09-24 18:06:27
合計ジャッジ時間 7,160 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
int ri() {
    int n;
    scanf("%d", &n);
    return n;
}
void out(long long n) {
    printf("%lld\n", n);
}
int main() {
    int m = ri();
    int n = ri();
    int mulx = ri();
    int addx = ri();
    int muly = ri();
    int addy = ri();
    int mod = ri();
    std::vector<int64_t> cnt(mod);
    {
        std::vector<int> x;
        std::vector<int> y;
        for (int i = 0; i < m; i++) x.push_back(ri());
        for (int i = 0; i < m; i++) y.push_back(ri());
        for (int i = 0; i < m; i++) cnt[x[i]] += y[i];
        int prev_x = x.back(), prev_y = y.back();
        for (int i = m; i < n; i++) {
            int new_x = ((int64_t) prev_x * mulx + addx) % mod;
            int new_y = ((int64_t) prev_y * muly + addy) % mod;
            cnt[new_x] += new_y;
            prev_x = new_x;
            prev_y = new_y;
        }
    }
    
    std::vector<int> primes;
    std::vector<bool> table(mod, true);
    for (int i = 2; i < mod; i++) if (table[i]) {
        primes.push_back(i);
        for (int j = i * 2; j < mod; j += i) table[j] = false;
    }
    for (auto i : primes) {
        int max = (mod - 1) / i;
        for (int j = max; j; j--) cnt[j] += cnt[j * i];
    }
    int64_t xored = 0;
    int prev_a, prev_b;
    {
        std::vector<int> a, b;
        for (int i = 0; i < m; i++) a.push_back(ri());
        for (int i = 0; i < m; i++) b.push_back(ri());
        for (int i = 0; i < m; i++) {
            int64_t res = cnt[a[i]];
            if ((int64_t) a[i] * b[i] < mod) res -= cnt[a[i] * b[i]];
            out(res);
            xored ^= res;
        }
        prev_a = a.back();
        prev_b = b.back();
    }
    for (int i = m; i < n; i++) {
        int new_a = ((int64_t) prev_a * mulx + addx + mod - 1) % mod + 1;
        int new_b = ((int64_t) prev_b * muly + addy + mod - 1) % mod + 1;
        int64_t res = cnt[new_a];
        if ((int64_t) new_a * new_b < mod) res -= cnt[new_a * new_b];
        xored ^= res;
        prev_a = new_a;
        prev_b = new_b;
    }
    out(xored);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0