問題一覧 > 通常問題

No.896 More Than Friends, Less Than Lovers

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 198 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 34
作問者 : Lepton_s / テスター : 37zigen
お気に入りにしたユーザー ProblemId : 2101 / 自分の提出
問題文最終更新日: 2026-10-22 18:36:02
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 225 (順位表) の他の問題:

Problem Statement

There are $N$ rabbits and $N$ kinds of eels.
The $j$-th rabbit considers an eel a friend if its Yukic◯der rating is a multiple of $a_j$, and considers an eel a lover if its rating is a multiple of $a_j \times b_j$.
There are $z_{x_i}$ eels with rating $x_i$.
For each rabbit, find the number of eels that are more than friends but less than lovers (that is, whose rating is a multiple of $a_j$ and not a multiple of $a_j \times b_j$).

($z_{x}$ = $\sum_{k: x_k=x} y_k$.
Consider that initially 0 eels have been found, and that each time $x_i$ $y_i$ is given as input, $y_i$ new eels with rating $x_i$ are found.)

Since Yukic◯der has a very large number of users, the input is generated by the following method.
(In the code below, X[i], Y[i], x[i], y[i], z[i], A[i], B[i], a[i], b[i] represent $X_i, Y_i, x_i, y_i, z_i, A_i, B_i, a_i, b_i$. for i in [L, R] means the same as for(int i = L; i <= R; i++).)
MOD is a power of 2 and can be written as MOD=$2^n$, and x % MOD can be computed as x & (MOD-1). (a%b is the remainder of a divided by b, and a&b is the bitwise and of a and b.)
The following is pseudocode of the algorithm that generates the input. Note that implementing the code below exactly as written may result in TLE or MLE. (Holding $2^{24}$ 64-bit variables consumes 128 MB.)

z[0] = z[1] = ... = z[MOD-1] = 0
for i in [1, M]:
    x[i] = X[i]
    y[i] = Y[i]
    a[i] = A[i]
    b[i] = B[i]
    
for i in [M+1, N]:
    x[i] = (x[i-1] * mulX + addX) % MOD
    y[i] = (y[i-1] * mulY + addY) % MOD
    a[i] = (a[i-1] * mulX + addX + MOD - 1) % MOD + 1
    b[i] = (b[i-1] * mulY + addY + MOD - 1) % MOD + 1

for i in [1, N]:
    z[x[i]] += y[i]
Also, since the output would otherwise be too long, print the answers directly only for the first $M$ rabbits, and on the last line print the exclusive OR of the answers of all rabbits.

Input

$M$ $N$ $mulX$ $addX$ $mulY$ $addY$ $MOD$
$X_1$ $\cdots$ $X_{M}$
$Y_1$ $\cdots$ $Y_{M}$
$A_1$ $\cdots$ $A_{M}$
$B_1$ $\cdots$ $B_{M}$

The first line contains $M$ $N$ $mulX$ $addX$ $mulY$ $addY$ $MOD$.
The second line contains $M$ input values $X_i$.
The third line contains $M$ input values $Y_i$.
The fourth line contains $M$ input values $A_i$.
The fifth line contains $M$ input values $B_i$.
All input values are integers.

$1$ $\le$ $M$ $\le$ $10^3$
$M$ $\le$ $N$ $\le$ $10^7$
$1$ $\le$ $MOD$ $\le$ $2^{24}$ ($MOD$ is a power of 2)
$0$ $\le$ $mulX$, $addX$, $mulY$, $addY$ $\lt$ $MOD$
$0$ $\le$ $X_i$, $Y_i$ $\lt$ $MOD$
$1$ $\le$ $A_j$, $B_j$ $\le$ $MOD$

Output

Output $M+1$ lines.
On the $j$-th of the first $M$ lines, print the number of eels that are more than friends but less than lovers for rabbit $j$, followed by a newline.
On line $M+1$, print the exclusive OR of the answers of all rabbits, followed by a newline.

Sample

Sample 1
Input
3 3 0 0 0 0 8
4 4 4
1 2 3
1 2 3
2 3 1
Output
0
6
0
6

There are 6 eels with rating 4.
For the 1st rabbit, all eels are both friends and lovers.
For the 2nd rabbit, all eels are more than friends but less than lovers.
For the 3rd rabbit, all eels are neither friends nor lovers.

Sample 2
Input
2 2 1 2 3 4 8
0 1
1 0
1 2
2 1
Output
0
0
0

0 is a multiple of every integer.

Sample 3
Input
1 10 1 1 1 1 32
1
2
3
4
Output
21
13

Sample 4
Input
1 8 5 3 0 2 16
1
5
2
6
Output
6
15

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。