需要存储每个质因数存在的位置,然后计算出每个质因数的贡献和。
题意
Mul(i,j)代表的是第i到j个数字的乘积,然后fac(i,j)代表这个乘积的不同的质因子的个数。现在让你求出n^2段区间内的fac(i,j)和.
思路
显然不能用N^2的做法。我们可以先把每个数字质因数分解,存储每个质因数所在的位置。比如说序列为22,33。 那么11这个质因数存在的位置就是1,2. 然后我们枚举每个质因数的每个存在的位置,计算贡献和。
1 |
|
云腾致雨,露结为霜
需要存储每个质因数存在的位置,然后计算出每个质因数的贡献和。
Mul(i,j)代表的是第i到j个数字的乘积,然后fac(i,j)代表这个乘积的不同的质因子的个数。现在让你求出n^2段区间内的fac(i,j)和.
显然不能用N^2的做法。我们可以先把每个数字质因数分解,存储每个质因数所在的位置。比如说序列为22,33。 那么11这个质因数存在的位置就是1,2. 然后我们枚举每个质因数的每个存在的位置,计算贡献和。
1 | #include <iostream> |