容斥.
首先考虑没平方因子的,他们对答案的贡献是1.
然后考虑至少有1个平方因子的,他们对答案的贡献是-1.
然后考虑至少有3个平方因子的,他们对答案的贡献是1…

如何快速统计一个数字有几个平方因子?
分块.
对于一个数字num,他的莫比乌斯函数代表的是不带平方数的-1的不同质数的个数次方.而num对于整个N的贡献是 $\lfloor\frac N{num^2}\rfloor$ (也就是所有区间至少包含这个平方因子的数的个数).

所以答案就是

Vibe Coding.

prompt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
帮我写一个c++代码，用于计算下面的式子：\sum_{i=1}^{\lfloor\sqrt{N}\rfloor}
\left\lfloor\dfrac{N}{i^2}\right\rfloor\cdot \mu(i)
其中mu是莫比乌斯函数，N的值是2^50。

程序的思路是，首先对N开根号（下取整即可），对sqN的范围进行欧拉筛，顺带求出mu的值，然后直接枚举i统计答案。
注意开long long。
我给你一个参考欧拉筛实现：

int   vis[1000010];//存最小质因数,负的表示质数表中的位置(负的)
int  p[100010],ptop=0;//存质数 
short  mu[1000010];//莫比乌斯函数 
void sieve(int n){//[1,n]
    mu[1]=1;
    int tmp;
    for(int i=2;i<=n;++i){
        if(!vis[i]){
            vis[i]=-(++ptop);
            p[ptop]=i;
            mu[i]=-1;//
        }
        for(int j=1;j<=ptop&&i*p[j]<=n;++j){
            vis[i*p[j]]=p[j];
            if(i%p[j]==0){
                break;
            }else{
                mu[i*p[j]]=-mu[i];//
            }
        }
    }
}

Gemini

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
好的，这道题的思路很清晰。$N = 2^{50}$，所以 $\lfloor\sqrt{N}\rfloor = 2^{25}$。
我们需要筛出 $1$ 到 $2^{25}$ 范围内的莫比乌斯函数 $\mu(k)$。

$2^{25} = 33,554,432$。

你给的欧拉筛模板中的数组大小（例如 `vis[1000010]`）是不够的，需要扩大到 $2^{25}$。
同时，素数表 `p` 的大小也需要扩大。根据素数定理，$\pi(x) \approx x/\ln(x)$，$\pi(3.3 \times 10^7) \approx 3.3 \times 10^7 / 17.3 \approx 1.9 \times 10^6$。所以素数表大小开到 `2,200,000` 左右比较安全。

以下是根据你的思路和要求实现的代码：

1.  **全局数组定义**：将 `vis`, `mu`, `p` 的大小调整以适应 $2^{25}$。
2.  **欧拉筛 `sieve` 函数**：
      * 基本沿用你的实现。
      * **重要**：在内层循环中，`i * p[j]` 可能会超过 `int` 的范围（尽管最终结果 `product` 不会超过 `n`，但中间计算 `i*p[j]` 时如果 `i` 和 `p[j]` 都很大，例如 $50000 \times 50000$，会先溢出再比较）。因此，`i * p[j]` 的比较和计算应使用 `long long` 来防止溢出。
      * 你的代码中 `mu[i*p[j]] = 0` 的情况是依赖于全局数组默认初始化为0，这是正确的。
3.  **`main` 函数**：
      * 定义 `N` 和 `sqN` 为 `long long` 类型。`1LL << 50` 和 `1LL << 25` 是计算它们的精确方式。
      * 调用 `sieve(sqN)`。
      * 循环 $k$ 从 $1$ 到 `sqN`，累加答案。
      * `k` 和 `ans` 必须使用 `long long`。在计算 `(N / (k * k))` 时，`k * k` 也会非常大，所以 `k` 必须是 `long long`。

-----

### C++ 完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>

// N = 2^50, sqrt(N) = 2^25 = 33,554,432
// 我们需要筛到 2^25
const int MAX_SQRT_N = 33554432 + 10; // 数组开大一点
// 质数数量估计 pi(3.3e7) approx 2.0e6
const int MAX_PRIMES = 2200000; 

// 使用全局数组，它们会自动初始化为0
int   vis[MAX_SQRT_N]; // 存最小质因数, 负的表示质数表中的位置(负的)
int   p[MAX_PRIMES], ptop = 0; // 存质数 
short mu[MAX_SQRT_N]; // 莫比乌斯函数

/**
 * @brief 欧拉筛法计算莫比乌斯函数
 * @param n 筛法上限 [1, n]
 */
void sieve(int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) {
            vis[i] = -(++ptop);
            p[ptop] = i;
            mu[i] = -1; // 质数的mu为-1
        }
        for (int j = 1; j <= ptop; ++j) {
            // 使用 long long 防止 i * p[j] 中间计算溢出
            long long product = (long long)i * p[j];
            if (product > n) {
                break;
            }
            
            // 此时 product 肯定在 int 范围内，因为 product <= n
            vis[product] = p[j]; // p[j] 是 product 的最小质因子
            
            if (i % p[j] == 0) {
                // i 包含了 p[j] 这个因子
                // product 包含了 p[j]^2 因子
                // mu[product] 默认为 0 (全局数组初始化)
                break;
            } else {
                // i 和 p[j] 互质 (p[j] < i的最小质因子)
                mu[product] = -mu[i];
            }
        }
    }
}

int main() {
    // 定义 N = 2^50
    long long N_VALUE = 1LL << 50;

    // 定义 N 的平方根下取整 sqN = 2^25
    long long sqN_VALUE = 1LL << 25; // 33,554,432

    // 运行筛法
    // (int)sqN_VALUE 是安全的，因为 2^25 在 int 范围内
    sieve((int)sqN_VALUE);

    long long ans = 0;
    
    // 循环 k 从 1 到 sqN
    // k 必须是 long long, 因为 k*k 会超过 int
    for (long long k = 1; k <= sqN_VALUE; ++k) {
        // ans += (N / (k*k)) * mu(k)
        ans += (N_VALUE / (k * k)) * mu[k];
    }

    // 输出最终答案
    std::cout << ans << std::endl;

    return 0;
}