結果

問題 No.896 友達以上恋人未満
ユーザー QCFiumQCFium
提出日時 2019-09-27 22:56:08
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 918 ms / 3,500 ms
コード長 1,923 bytes
コンパイル時間 1,942 ms
コンパイル使用メモリ 172,824 KB
実行使用メモリ 136,548 KB
最終ジャッジ日時 2024-09-25 00:53:18
合計ジャッジ時間 4,721 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 205 ms
36,596 KB
testcase_06 AC 492 ms
36,664 KB
testcase_07 AC 211 ms
36,748 KB
testcase_08 AC 207 ms
36,588 KB
testcase_09 AC 405 ms
69,868 KB
testcase_10 AC 918 ms
136,548 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:84:48: warning: 'prev_b' may be used uninitialized [-Wmaybe-uninitialized]
   84 |                 int new_b = (((int64_t) prev_b * muly + addy + mod - 1) & mask) + 1;
      |                               ~~~~~~~~~~~~~~~~~^~~~~~
main.cpp:69:21: note: 'prev_b' was declared here
   69 |         int prev_a, prev_b;
      |                     ^~~~~~
main.cpp:54:55: warning: 'prev_y' may be used uninitialized [-Wmaybe-uninitialized]
   54 |                         int new_y = ((int64_t) prev_y * muly + addy) & mask;
      |                                      ~~~~~~~~~~~~~~~~~^~~~~~
main.cpp:47:40: note: 'prev_y' was declared here
   47 |                 int 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, s = 0;
	while (1) {
		c = getchar();
		if (c == '-') {
			s = 1;
			break;
		}
		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 s ? -r : r;
}

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();
	int mask = mod - 1;
	std::vector<int64_t> cnt(mod);
	{
		std::vector<int> x(m);
		for (int i = 0; i < m; i++) x[i] = ri();
		int 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++) {
			int new_x = ((int64_t) prev_x * mulx + addx) & mask;
			int new_y = ((int64_t) prev_y * muly + addy) & mask;
			cnt[new_x] += new_y;
			prev_x = new_x;
			prev_y = new_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;
	int 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++) {
		int new_a = (((int64_t) prev_a * mulx + addx + mod - 1) & mask) + 1;
		int new_b = (((int64_t) prev_b * muly + addy + mod - 1) & mask) + 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