結果

問題 No.896 友達以上恋人未満
ユーザー QCFiumQCFium
提出日時 2019-09-27 22:22:55
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 544 ms
38,864 KB
testcase_06 AC 1,405 ms
38,740 KB
testcase_07 AC 557 ms
38,660 KB
testcase_08 AC 551 ms
38,868 KB
testcase_09 AC 765 ms
74,324 KB
testcase_10 AC 1,158 ms
144,852 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
0