結果

問題 No.896 友達以上恋人未満
ユーザー QCFiumQCFium
提出日時 2019-09-27 23:07:04
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 986 ms / 3,500 ms
コード長 1,781 bytes
コンパイル時間 1,617 ms
コンパイル使用メモリ 172,784 KB
実行使用メモリ 136,504 KB
最終ジャッジ日時 2023-10-25 05:55:55
合計ジャッジ時間 4,845 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 216 ms
36,580 KB
testcase_06 AC 500 ms
36,580 KB
testcase_07 AC 222 ms
36,580 KB
testcase_08 AC 219 ms
36,580 KB
testcase_09 AC 446 ms
69,812 KB
testcase_10 AC 986 ms
136,504 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:78:35: warning: 'prev_b' may be used uninitialized [-Wmaybe-uninitialized]
   78 |                 prev_b = ((prev_b * muly + addy + mod - 1) & mask) + 1;
      |                            ~~~~~~~^~~~~~
main.cpp:63:26: note: 'prev_b' was declared here
   63 |         uint32_t prev_a, prev_b;
      |                          ^~~~~~
main.cpp:50:42: warning: 'prev_y' may be used uninitialized [-Wmaybe-uninitialized]
   50 |                         prev_y = (prev_y * muly + addy) & mask;
      |                                   ~~~~~~~^~~~~~
main.cpp:43:45: note: 'prev_y' was declared here
   43 |                 uint32_t prev_x = x.back(), prev_y;
      |                                             ^~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>

#ifdef WIN32
#define getchar_fast _getchar_nolock
#else
#define getchar_fast getchar_unlocked
#endif

int ri() {
	int c, r = 0;
	while (1) {
		c = getchar();
		if (c >= '0' && c <= '9') {
			r = c - '0';
			break;
		}
	}
	while (1) {
		c = getchar();
		if (c < '0' || c > '9') break;
		r = r * 10 + c - '0';
	}
	return r;
}

void out(long long n) {
	printf("%lld\n", n);
}

int main() {
	int m = ri();
	int n = ri();
	uint32_t mulx = ri();
	uint32_t addx = ri();
	uint32_t muly = ri();
	uint32_t addy = ri();
	int mod = ri();
	uint32_t mask = mod - 1;
	std::vector<int64_t> cnt(mod);
	{
		std::vector<int> x(m);
		for (int i = 0; i < m; i++) x[i] = ri();
		uint32_t prev_x = x.back(), prev_y;
		for (int i = 0; i < m; i++) {
			int y = prev_y = ri();
			cnt[x[i]] += y;
		}
		for (int i = m; i < n; i++) {
			prev_x = (prev_x * mulx + addx) & mask;
			prev_y = (prev_y * muly + addy) & mask;
			cnt[prev_x] += prev_y;
		}
	}
	
	std::vector<bool> table(mod, true);
	for (int i = 2; i < mod; i++) if (table[i]) {
		for (int j = i * 2; j < mod; j += i) table[j] = false;
		int max = (mod - 1) / i;
		for (int j = max; j; j--) cnt[j] += cnt[j * i];
	}
	
	int64_t xored = 0;
	uint32_t prev_a, prev_b;
	{
		std::vector<int> a(m);
		for (int i = 0; i < m; i++) a[i] = ri();
		for (int i = 0; i < m; i++) {
			int b = prev_b = ri();
			int64_t res = cnt[a[i]];
			if ((int64_t) a[i] * b < mod) res -= cnt[a[i] * b];
			xored ^= res;
			out(res);
		}
		prev_a = a.back();
	}
	for (int i = m; i < n; i++) {
		prev_a = ((prev_a * mulx + addx + mod - 1) & mask) + 1;
		prev_b = ((prev_b * muly + addy + mod - 1) & mask) + 1;
		int64_t res = cnt[prev_a];
		if ((int64_t) prev_a * prev_b < mod) res -= cnt[prev_a * prev_b];
		xored ^= res;
	}
	out(xored);
	return 0;
}
0