#1178622 (C++14) No.896 友達以上恋人未満

• 問題: No.896 友達以上恋人未満
• ユーザー: zelda_master
• 提出日時: 2026-08-23 22:42:36
• 言語: C++14 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 1,237 ms / 3,500 ms
• コード長: 4,181 bytes
• コンパイル時間: 311 ms
• コンパイル使用メモリ: 77,136 KB
• 実行使用メモリ: 81,824 KB
• 最終ジャッジ日時: 2026-08-23 22:42:42
• 合計ジャッジ時間: 5,199 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 4
other	AC * 7

ソースコード

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 1 << 24, M = 1010;

int m, n, mul_x, add_x, mul_y, add_y, MOD, x[M];
int last_x, last_y, last_a, last_b; // 四个递推序列的当前项
LL z[N]; // 先存各评级数量，随后原地改为对应评级的正倍数和

/**
 * 问题：给定各评级的带权出现次数，对每组 $(a,b)$ 求评级是 $a$ 的倍数、
 *       但不是 $ab$ 的倍数的总权值；数据与询问的后缀由递推式生成。
 *
 * 线索：
 *   - $N\le 10^7$，不能保存四个长度为 $N$ 的生成序列。
 *   - $MOD\le 2^{24}$，一个长度为 $MOD$ 的 64 位数组约占 128 MB。
 *   - 每次询问只关心某两个数的所有倍数，可以统一预处理倍数和。
 *
 * 思维链：
 *   1. 生成式只依赖前一项，因此流式生成 $(x_i,y_i)$，直接累加到 $z[x_i]$。
 *   2. 定义 $S(d)=\sum_{k\ge 1,\,kd<MOD}z[kd]$，则答案为
 *      $S(a)-S(ab)$；评级 0 在两项中同时出现，恰好抵消。
 *   3. 将 $S(d)$ 原地写回 $z[d]$。按 $d$ 从小到大计算时，所读取的
 *      $z[2d],z[3d],\ldots$ 尚未被改写，因而不会重复统计。
 *   4. 预处理结束后，从显式前缀的末项继续生成 $(a_i,b_i)$，边生成边异或。
 *
 * 关键性质：
 *   - 对 $d\ge MOD$，除评级 0 外没有合法倍数，因此忽略 0 后 $S(d)=0$。
 *   - 当 $d\ge MOD/2$ 时，区间内不存在 $2d$，故 $S(d)=z[d]$，无需更新。
 *   - $MOD$ 是 2 的整数次幂，所以对非负数取模可写成与 $MOD-1$ 按位与。
 *
 * 核心思路：
 *   1. 流式生成全部鳗鱼数据，建立评级计数数组 $z$。
 *   2. 枚举每个较小的 $d$，累加其所有正倍数，将 $z[d]$ 改为 $S(d)$。
 *   3. 对显式询问直接输出答案，再流式生成剩余询问并维护答案异或和。
 *
 * 时间复杂度：$\mathcal{O}(N+MOD\log MOD)$
 *
 * 其他思路：
 *   1. 离线标记询问实际出现的所有 $a$ 与 $ab$，只对不同的有效 $d$
 *      枚举倍数。复杂度为
 *      $\mathcal{O}(N+\sum_{d\in D}\lfloor(MOD-1)/d\rfloor)$，
 *      最坏仍为 $\mathcal{O}(N+MOD\log MOD)$。
 */
int main() {
    // freopen("friend.in", "r", stdin);
    // freopen("friend.out", "w", stdout);

    // 步骤1：读入显式的 x、y 前缀，并直接累计每种评级的鳗鱼数量
    scanf("%d%d%d%d%d%d%d", &m, &n, &mul_x, &add_x, &mul_y, &add_y, &MOD);
    for (int i = 1; i <= m; ++i) scanf("%d", &x[i]);
    for (int i = 1; i <= m; ++i) {
        scanf("%d", &last_y);
        z[x[i]] += last_y;
    }

    // 步骤2：只维护递推序列的末项，流式生成剩余的 x、y
    last_x = x[m];
    for (int i = m + 1; i <= n; ++i) {
        last_x = (1LL * last_x * mul_x + add_x) & (MOD - 1);
        last_y = (1LL * last_y * mul_y + add_y) & (MOD - 1);
        z[last_x] += last_y;
    }

    // 步骤3：评级 0 在朋友数与恋人数中抵消，再原地预处理每个 d 的正倍数和
    z[0] = 0LL;
    for (int i = 1; i < MOD / 2; ++i) {
        for (int j = 2 * i; j < MOD; j += i) z[i] += z[j];
    }

    // 步骤4：读入并回答前 m 个显式询问，同时计入全部答案的异或和
    for (int i = 1; i <= m; ++i) scanf("%d", &x[i]);
    LL ans = 0LL;
    for (int i = 1; i <= m; ++i) {
        scanf("%d", &last_b);
        LL now = x[i] < MOD ? z[x[i]] : 0LL;
        // 乘积越界值域时，其正倍数和为 0，也不能作为 z 的下标
        if (1LL * x[i] * last_b < MOD) now -= z[x[i] * last_b];
        ans ^= now;
        printf("%lld\n", now);
    }

    // 步骤5：从前缀末项继续生成询问，避免保存后 n-m 对 a、b
    last_a = x[m];
    for (int i = m + 1; i <= n; ++i) {
        last_a = (1LL * last_a * mul_x + add_x + MOD - 1) & (MOD - 1);
        last_b = (1LL * last_b * mul_y + add_y + MOD - 1) & (MOD - 1);
        ++last_a, ++last_b;
        LL now = last_a < MOD ? z[last_a] : 0LL;
        if (1LL * last_a * last_b < MOD) now -= z[last_a * last_b];
        ans ^= now;
    }

    // 步骤6：输出全部 n 个答案的按位异或和
    printf("%lld\n", ans);

    return 0;
}