csp2021阅读程序#8211;欧拉筛求1到N之间所有数字的约数个数与约数之和
欧拉筛求约数个数及约数之和
Format
Input
给你一个数字t,代表有t组询问
每组询问给你一个数字x,请输出x的约数个数及约数之和
t<=1e6
x<=1e7
Output
输出t行，含义如上
Samples
输入数据 1
3
1
100
120
输出数据 1
1 1
9 217
16 360
Sol:此题需要对欧拉筛有较深的理解
其为了保证每个数字只被删除一次，用到了这样一个简单的事实：
对于每个数字来说，其较大的因子总是唯一的
例如12=2*6，6就是12较大的因子，与之相对应的那个2则是12的最小的质因子“
大家可以再结合
20=2*10
21=3*7
来进行理解
20是当我们在外层枚举到10时，内层枚举到2时，将20打上非质数的标记的
21是当我们在外层枚举到7时，内层枚举到3时，将21打上非质数的标记的.
也就是说内层所枚举的数字(设之为K），是i*k这个数字最小的质因子
于是根据i%k是否等于0，可以分成两种情况 来进行讨论
1：i%k==0,于是对于i*k来说，k这个质因子从前在i中就出现了。
于是在计算i*k的约数个数及约数之和时，可以从i的约数个数及约数之和进行简单推导得来
2：i%k！=0,于是对于i*k来说，k这个质因子从前没有在i中就出现了。
于是在计算i*k的约数个数及约数之和时，可以从i的约数个数及约数之和进行简单推导得来
以下面的例子来说明 一下
当i%k==0时，不妨设i=12,k=2
f(12)=(1+2)*(1+1)=6
f(24)=(1+3)*(1+1)=8
c(24)=3
于是f(24)=f(12)/c(24) * (c(24)+1)
=6/3*4=8
当i=6,k=2时
g(6)=(1+2)*(1+3)
d(6)=(1+3)
下个直观点，但多一个循环来算K^c[i*K)
g(12)=(1+2+4)*(1+3)
=(1+2)*(1+3)+4*(1+3)
=g(6)+2^2*(1+3)
=g(6)+k^c(12)*(1+3)
这个需要推导下，可读性不是太好
g(12)=(1+2+4)(1+3)
=(1+3)+(2+4)(1+3)
=(1+3)+2(1+2)*(1+3)
=d(6)+k*g(6)
当i%k!=0时,此时要注意k为i*k最小的质因子
例如当i=15,k=2时
f[i * k] = 2 * f[i]...这个好理解的，因为多了一个新的质因子出来了，且指数为1
d[i * k] = g[i]...对于i*k来说，它最小的质因子为k,于是在d数组含义的约定下
其就等于g[i]
g[i * k] = g[i] * (k + 1)...约数之和，这个也好理解，不说了
#include <iostream>
using namespace std;
const int n = 1e7;
const int N = n + 1;
int m;
int a[N], b[N], c[N], d[N];
int f[N], g[N];
int mul(int a,int b)
{
int s=1;
for (int i=1;i<=b;i++)
s=s*a;
return s;
}
void init()
{
f[1] = g[1] = 1;
for (int i = 2; i <= n; i++)
{
if (!a[i])
//如果i不是质数的话，加入质数队列
{
b[m++] = i;
//队列中第m个质数为i
c[i] = 1, f[i] = 2;
//c[i]用来记对于i来说，其最小的质因子的指数
//f[i]用来记i的约数个数，对于质数来说，它有2个约数
d[i] = 1, g[i] = i + 1;
//d[i]用来记录对于数字i求质因子之和那个连乘表达式中，去掉，最小质因子那段连乘之和之后的，那一段
//例如g[6]=(1+2)*(1+3),则d[6]=(1+3)
//g[i]用于记录i的质因子之和
}
for (int j = 0; j < m && b[j] * i <= n; j++)
//枚举质数队列，从小到大
{
int k = b[j];
a[i * k] = 1;
//标记i*k不是质数
if (i % k == 0)
//如果k是i最小的质因子的话
{
c[i * k] = c[i] + 1;
//指数增加1
f[i * k] = f[i] / c[i * k] * (c[i * k] + 1);
//约数个数变化，详见图1
d[i * k] = d[i];
//d[i*k]与d[i]保持一致
g[i*k]=g[i]+mul(k,c[i*k])*d[i];
//当i=12,k=2时
//例如g(12*2)=g(24)=(1+2+4+8）*（1+3)
// =(1+2+4)*(1+3)+8*(1+3)
// =g(12)+k^c(24)*d(12)
//写成上面这样的方式更易理解
//当然，写成下面这个，也可以，但需要一些推导
// g[i * k] = g[i] * k + d[i];
//质因子之和发生变化，详见图2
break;
}
else
{
c[i * k] = 1;
//k做为i*k的最小质因子，现在出现了1次
f[i * k] = 2 * f[i];
//约数个数发生变化
d[i * k] = g[i];
//对于i*k来说，d[i*k]就是从前g[i]的表达式，因为k是i*k的最小质因子
g[i * k] = g[i] * (k + 1);
//约数之和发生变化
}
}
}
}
int main() {
init();
int tot;
cin>>tot;
int x;
while(tot--){
cin>>x;
cout<<f[x]<<' '<<g[x]<<endl;
}
return 0;
}