#P5455. spoj DIVCNT2

    ID: 4461 传统题 20000ms 512MiB 尝试: 53 已通过: 27 难度: 8 上传者: 标签>难度分类提高+/省选-数论Min_25 筛整除分块约数个数乘积公式埃氏筛素数计数CF2500

spoj DIVCNT2

[SPOJ] DIVCNT2 - 平方数的因子计数

题目描述

令 σ0(n)\sigma_0(n) 表示正整数 nn 的正因子个数。例如 σ0(1)=1\sigma_0(1)=1、σ0(2)=2\sigma_0(2)=2、σ0(6)=4\sigma_0(6)=4。

给定 NN,求

S2(N)=∑i=1Nσ0(i2).S_2(N)=\sum_{i=1}^N \sigma_0(i^2).

输入格式

第一行一个整数 TT,表示数据组数。接下来 TT 行,每行一个正整数 NN。

输出格式

每组数据输出一行一个整数,表示对应的 S2(N)S_2(N)。

样例

5
1
2
3
10
100
1
4
7
48
1194

$S_2(3)=\sigma_0(1^2)+\sigma_0(2^2)+\sigma_0(3^2)=1+3+3=7$。

数据范围

SPOJ 原题的总范围为 1≤T≤100001\le T\le10000、1≤N≤10121\le N\le10^{12},源代码大小限制为 6 KiB。原题分组如下。

原题输入文件 附加限制 原题时间限制
1 N≤10000N\le10000 1 秒
2 T≤800T\le800,N≤108N\le10^8 20 秒
3 T≤200T\le200,N≤109N\le10^9
4 T≤40T\le40,N≤1010N\le10^{10}
5 T≤10T\le10,N≤1011N\le10^{11}
6 T=1T=1,N≤1012N\le10^{12}

本题允许 T=0T=0,此时输出为空。使用 64 位整数读取 NN 和保存答案。

SPOJ 原题