programming-notes

题目整理：因子个数为奇数的数量

题目描述

给定一个正整数 n，求区间 [1, n] 中”因子个数为奇数”的正整数的个数。

输入描述

本题有多组数据： - 第一行一个整数 T (1 ≤ T ≤ 10\^3)，表示数据组数\

• 每组一行一个整数 n (1 ≤ n ≤ 4 × 10\^3)

输出描述

每组输出一个整数，表示答案。

样例输入

4
1
10
100
1000

样例输出

1
3
10
31

---

解题思路

1. 关键结论

一个正整数的因子个数为奇数 当且仅当它是一个完全平方数。

2. 为什么？

一般来说，因子是成对出现的： - 若 d 是 n 的因子，则 n/d 也是因子

只有当： - d = n/d → 即 d² = n - 此时因子不会成对出现，而是”重复中间项”

因此只有完全平方数才会出现”中间因子”，导致因子个数为奇数。

3. 问题转化

题目变为： > 统计 [1, n] 中完全平方数的个数

也就是： > ⌊√n⌋

---

解法

对于每个 n：

ans = (int) sqrt(n)

时间复杂度： - 每组 O(1)

---

Java代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        while (T-- > 0) {
            int n = in.nextInt();
            System.out.println((int)Math.sqrt(n));
        }
    }
}

---

总结

• 核心：因子成对出现
• 只有完全平方数例外
• 答案 = √n 向下取整

This site is open source. Improve this page.