思路

我们要求解的目标是 $S = \sum_{i=1}^{n} \sigma(i)$ 的奇偶性，其中 $\sigma(i)$ 表示正整数 $i$ 的所有正因子之和。

一个和的奇偶性取决于其中奇数项的个数。如果奇数项的个数是奇数，那么和就是奇数；如果奇数项的个数是偶数，那么和就是偶数。因此，问题转化为：在区间 $[1, n]$ 中，有多少个整数 $i$ 使得 $\sigma(i)$ 是奇数。设这个数量为 $C$，我们最终要求的就是 $C \pmod 2$。

接下来我们分析 $\sigma(i)$ 为奇数的条件。 一个整数 $i$ 的标准素数分解为 $i = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$。 其正因子之和的公式为： $\sigma(i)$ = ($1$ + $p_1$ + $\dots$ + $p_1^{a_1}$)($1$ + $p_2$ + $\dots$ + $p_2^{a_2}$) $\cdots$ ($1$ + $p_k$ + $\dots$ + $p_k^{a_k}$) 为了使 $\sigma(i)$ 为奇数，上式中的每一个连乘项都必须是奇数。

我们对每个连乘项 $(1 + p + \dots + p^a)$ 进行分析：

1. 如果 $p=2$，该项为 $1 + 2 + \dots + 2^a = 2^{a+1} - 1$，这总是一个奇数，与指数 $a$ 无关。
2. 如果 $p$ 是一个奇素数，那么 $1, p, p^2, \dots, p^a$ 都是奇数。这个和共有 $a+1$ 个奇数。$a+1$ 个奇数相加，其和为奇数的充要条件是项数 $a+1$ 是奇数，这意味着指数 $a$ 必须是偶数。

综上所述，$\sigma(i)$ 为奇数的充要条件是：在 $i$ 的素数分解中，所有奇素数因子的指数都必须是偶数。 这样的数 $i$ 可以写成 $i = 2^k \cdot m$，其中 $m$ 的所有素因子都是奇数且指数都为偶数，这意味着 $m$ 本身是一个完全平方数。所以，$i$ 必须具有 $i = 2^k \cdot j^2$ 的形式（其中 $j$ 是某个正整数）。

我们进一步分析 $i = 2^k \cdot j^2$ 的形式：

• 如果 $k$ 是偶数，令 $k=2b$，那么 $i = 2^{2b} \cdot j^2 = (2^b \cdot j)^2$。这说明 $i$ 是一个完全平方数。
• 如果 $k$ 是奇数，令 $k=2b+1$，那么 $i = 2^{2b+1} \cdot j^2 = 2 \cdot (2^b \cdot j)^2$。这说明 $i$ 是一个完全平方数的两倍。

因此，$\sigma(i)$ 是奇数，当且仅当 $i$ 是一个完全平方数，或者是两倍的完全平方数。

现在问题转化为，计算在 $[1, n]$ 中有多少个数是完全平方数或两倍的完全平方数。

1. 在 $[1, n]$ 中的完全平方数有：$1^2, 2^2, 3^2, \dots, k^2$ 满足 $k^2 \leq n$。这样的 $k$ 有 $\lfloor \sqrt{n} \rfloor$ 个。
2. 在 $[1, n]$ 中的两倍的完全平方数有：$2 \cdot 1^2, 2 \cdot 2^2, \dots, 2 \cdot m^2$ 满足 $2m^2 \leq n$。这等价于 $m^2 \leq n/2$，所以这样的 $m$ 有 $\lfloor \sqrt{n/2} \rfloor$ 个。

一个数不可能是同时既是完全平方数又是两倍的完全平方数（除非是0，但我们考虑正整数），因为如果 $x^2 = 2y^2$，那么 $(x/y)^2 = 2$，这意味着 $\sqrt{2}$ 是有理数，这是矛盾的。 所以，在 $[1, n]$ 中使 $\sigma(i)$ 为奇数的整数个数 $C$ 为： $C$ = $\lfloor \sqrt{n} \rfloor$ + $\lfloor \sqrt{n/2} \rfloor$ 我们最终的答案就是 $C \pmod 2$，即 ($\lfloor \sqrt{n} \rfloor$ + $\lfloor \sqrt{n/2} \rfloor$) $\pmod 2$。

由于 $n$ 的值可以达到 $10^{18}$，在计算平方根时需要使用能够处理大数的整数类型和函数，以避免精度问题和溢出。

C++

#include <iostream>
#include <cmath>

// 使用 `unsigned __int128` 来避免 `long long` 相乘时溢出
// 这是一个GCC/Clang的扩展，但在大多数竞赛平台都支持
// 函数计算 n 的整数平方根，即 floor(sqrt(n))
long long integer_sqrt(long long n) {
    if (n < 0) return 0;
    if (n == 0) return 0;
    
    // 使用 long double 以获得更高的精度，作为初始猜测
    long long root = sqrtl(n);
    
    // 由于浮点数精度问题，结果可能偏大，需要向下调整
    while ((unsigned __int128)root * root > n) {
        root--;
    }
    // 结果也可能偏小，需要向上调整
    while ((unsigned __int128)(root + 1) * (root + 1) <= n) {
        root++;
    }
    return root;
}

void solve() {
    long long n;
    std::cin >> n;
    long long count1 = integer_sqrt(n);
    long long count2 = integer_sqrt(n / 2);
    long long total_count = count1 + count2;
    std::cout << total_count % 2 << std::endl;
}

int main() {
    // 提高cin/cout效率
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Python

import sys
import math

# 为了处理大规模输入，使用快速IO
def fast_input():
    return sys.stdin.readline().strip()

def solve():
    """
    解决单个测试用例
    """
    try:
        n_str = fast_input()
        if not n_str:
            return
        n = int(n_str)
        
        # math.isqrt(x) 直接计算 floor(sqrt(x))，高效且精确
        # Python的整数类型支持任意精度，所以不用担心中间计算溢出
        count1 = math.isqrt(n)
        count2 = math.isqrt(n // 2)  # 使用 // 进行整数除法
        
        total_count = count1 + count2
        
        print(total_count % 2)

    except (IOError, ValueError):
        # 处理可能的输入错误或文件结束
        return

def main():
    """
    主函数，处理多组测试数据
    """
    try:
        t_str = fast_input()
        if not t_str:
            return
        t = int(t_str)
        for _ in range(t):
            solve()
    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    /**
     * 计算整数 n 的整数平方根，即 floor(sqrt(n))。
     * @param n 一个非负长整型数。
     * @return n 的整数平方根。
     */
    public static long integerSqrt(long n) {
        if (n < 0) return 0;
        if (n == 0) return 0;

        // 使用 Math.sqrt() 得到一个浮点数作为初始猜测值
        // 这通常非常接近真实结果
        long root = (long) Math.sqrt(n);

        // 校正阶段：
        // 1. 如果猜测值过大 (root * root > n)，向下调整。
        //    为了避免 root * root 溢出，使用除法 root > n / root 来判断。
        //    这个判断对于正数是等价且安全的。
        while (root > 0 && root > n / root) {
            root--;
        }
        
        // 2. 如果猜测值过小 ((root + 1) * (root + 1) <= n)，向上调整。
        //    同样使用除法 (root + 1) <= n / (root + 1) 来避免溢出。
        while ((root + 1) <= n / (root + 1)) {
            // 这个条件也要小心，如果 root + 1 溢出变成负数，判断会出错。
            // 但因为 root 的初始值是 sqrt(n)，远小于 Long.MAX_VALUE，所以 root+1 不会溢出。
            root++;
        }
        
        return root;
    }

    public static void solve(FastReader sc, StringBuilder sb) {
        long n = sc.nextLong();
        
        long count1 = integerSqrt(n);
        long count2 = integerSqrt(n / 2);
        
        long totalCount = count1 + count2;
        
        sb.append(totalCount % 2).append("\n");
    }

    public static void main(String[] args) {
        FastReader sc = new FastReader();
        // 使用 StringBuilder 汇总所有输出，最后一次性打印，以提高效率
        StringBuilder sb = new StringBuilder();
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc, sb);
        }
        System.out.print(sb.toString());
    }

    // 用于快速读取输入的静态内部类
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}

题目内容

给定一个正整数$n$。对于区间$[1,n]$，求区间内所有整数的正因子之和的奇偶性。

因子:对于正整数$x$，如果存在正整数$p$使得$x$能被$P$整除，则称$p$是$x$的因子。例如，$12$的因子有$1,2,3,4,6,12$

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≦T≦2×10^4)$表示数据组数;

此后$T$行,每行输入一个整数$n(1≦n≦10^{18})$。

输出描述

对于每组测试数据，新起一行，输出一个整数，表示区间$[1,n]$内所有整数的正因子之和的奇偶性：奇数输出$1$，偶数输出$0$

样例1

输入

5
1 
2
3 
4
8

输出

1
0
0
1
0

说明

• 当$n=1$时:$1$的因子只有$1$，总和为$1$(奇数)，输出$1$;
• 当$n=2$时:在$n=1$的基础上再加上$2$的因子 $1、2$，总和变为$4$(偶数)，输出$0$;
• 当$n=3$时:再加上$3$的因子$1、3$，总和变为$8$(偶数)，输出$0$;
• 当$n=4$时:再加上$4$的因子$1、2、4$，总和变为$15$(奇数)，输出$1$;