解题思路

设第 $j$ 盏灯被按的总次数为 $t(j)$。第 $i$ 个人会在 $i\mid j$ 或 $j\mid i$ 时按一次。

对固定的 $j$：

• 由“有人是 $j$ 的约数”带来的次数：满足 $i\mid j$ 且 $1\le i\le m$ 的个数，记为 $d_{\le m}(j)$。
• 由“有人是 $j$ 的倍数”带来的次数：满足 $j\mid i$ 且 $1\le i\le m$ 的个数，为 $\left\lfloor \frac{m}{j}\right\rfloor$。
• 两者交集只在 $i=j$ 时出现（当且仅当 $j\le m$），被双计了一次，需要减去 1 次。

因此：

只关心奇偶性（是否为奇数），把三项逐一按位异或（$\bmod~2$）即可。

实现上：

• 用“筛法”累加 $d_{\le m}(j)$ 的奇偶：对所有 $i=1\ldots \min(m,n)$，把其所有倍数 $k\le n$ 的灯的奇偶翻转一次（等价于给所有满足 $i\mid k$ 的灯加 1 次）。
• 再对每个 $j$ 异或上 $(\lfloor m/j\rfloor\ \bmod 2)$。
• 若 $j\le m$，再异或 1（对应减去交集）。

最后统计奇数次的灯数即答案。

相关算法：整除筛（类似计算约数个数的线性/朴素筛的思想），按奇偶累计避免大数计数。

代码实现

Python

# -*- coding: utf-8 -*-
import sys

def solve_case(n, m):
    # 使用字节数组保存奇偶（0/1）
    parity = bytearray(n + 1)

    # 1) 累加 d_{<=m}(j) 的奇偶：对 i 的所有倍数翻转
    lim = n if m >= n else int(m)
    for i in range(1, lim + 1):
        step = i
        k = i
        p = parity  # 局部变量加速
        while k <= n:
            p[k] ^= 1  # 翻转一次
            k += step

    # 2) 对每个 j，叠加 floor(m/j) 的奇偶
    # 3) 若 j <= m，再异或 1（减交集）
    ans = 0
    jm = m  # 减少属性查找
    for j in range(1, n + 1):
        parity[j] ^= (jm // j) & 1
        if j <= jm:
            parity[j] ^= 1
        ans += parity[j]

    return ans

def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    T = int(next(it))
    out_lines = []
    for _ in range(T):
        n = int(next(it)); m = int(next(it))
        out_lines.append(str(solve_case(n, m)))
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

// 注意：类名必须为 Main（ACM 风格）
import java.io.*;
import java.util.*;

public class Main {
    // 解决单组：返回答案
    static long solveCase(int n, long m) {
        byte[] parity = new byte[n + 1];

        int lim = (m >= n) ? n : (int)m;

        // 1) 累加 d_{<=m}(j) 的奇偶：对 i 的倍数翻转
        for (int i = 1; i <= lim; i++) {
            for (int k = i; k <= n; k += i) {
                parity[k] ^= 1;
            }
        }

        // 2) floor(m/j) 的奇偶
        // 3) j <= m 的交集修正
        long ans = 0;
        for (int j = 1; j <= n; j++) {
            parity[j] ^= ( ( (m / j) & 1L ) == 1L ) ? 1 : 0;
            if ((long)j <= m) parity[j] ^= 1;
            ans += parity[j];
        }
        return ans;
    }

    // 快读（根据数据范围使用）
    static final class FastScanner {
        private final InputStream in;
        private final byte[] buf = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buf[ptr++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= ' ');
            if (c == '-') { sgn = -1; c = read(); }
            while (c > ' ') { x = x * 10 + (c - '0'); c = read(); }
            return x * sgn;
        }
        long nextLong() throws IOException {
            int c; long x = 0; int sgn = 1;
            do { c = read(); } while (c <= ' ');
            if (c == '-') { sgn = -1; c = read(); }
            while (c > ' ') { x = x * 10 + (c - '0'); c = read(); }
            return x * sgn;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder sb = new StringBuilder();
        int T = fs.nextInt();
        for (int t = 0; t < T; t++) {
            int n = fs.nextInt();
            long m = fs.nextLong();
            sb.append(solveCase(n, m)).append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

// ACM 风格：主函数读写，核心逻辑在外部函数
#include <bits/stdc++.h>
using namespace std;

// 解决单组：返回答案
long long solve_case(int n, long long m) {
    vector<unsigned char> parity(n + 1, 0);

    int lim = (m >= n) ? n : (int)m;

    // 1) 累加 d_{<=m}(j) 的奇偶：对 i 的所有倍数翻转
    for (int i = 1; i <= lim; ++i) {
        for (int k = i; k <= n; k += i) {
            parity[k] ^= 1;
        }
    }

    // 2) floor(m/j) 的奇偶
    // 3) 交集修正：j <= m 时再异或 1
    long long ans = 0;
    for (int j = 1; j <= n; ++j) {
        parity[j] ^= ( (m / j) & 1LL ) ? 1 : 0;
        if ((long long)j <= m) parity[j] ^= 1;
        ans += parity[j];
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int n;
        long long m;
        cin >> n >> m;
        cout << solve_case(n, m) << "\n";
    }
    return 0;
}

题目内容

给有$n$盏灯(编号$1$~$n$)，初始均为关闭状态。现有$m$个人(编号$1$~$m$)，第$i$个人会对所有满足$i\ |\ j$或$j\ |\ i$的灯$j$各按一次开关。按一次开关指切换灯的当前状态(开变关，关变开)。

请在所有人按完后，输出最终亮着的灯的数量。

[名词解释]

整除符号: $i\ |\ j$表示$i$整除$j$(即$j\ mod\ i =0$)，$i \nmid j$表示不整除;“$i\ |\ j$或j$j\ | \ i$"指二者存在因倍关系之一。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T (1≦T≦10^5)$表示数据组数。每组测试数据描述如下:

一行输入两个整数

$n,m (1≦n≦10,1≦m ≤10^{18})$

保证所有测试中$n$的总和不超过$2×10^6$

输出描述

输出$T$行，每行输出一个整数，表示所有人按完后仍然亮着的灯的数量

样例1

输入

3
5 3
4 1
6 2

输出

2
4 
2

说明

样例一: $n =5,m =3$。计算可得仅$j= 1,5$ 为开，答案$2$。

样例二: $m=1$时仅第$1$个人操作，因$1\ |\ j$对所有$j$成立，所有灯都被按一次，全部点亮，答案$4$。

样例三: $n =6,m =2$，最终仅$j=3,5$ 为开，答案$2$。