13th.Feb.2019
T1
好像问题挺简单的，来看看数据范围吧……
有没有点刚开始很欣喜后来有些恼火的感觉？那就对啦
：诶，这题我会n^2写法，20分呀，啊哦
：诶，我傻了，每个数求一下因数，n*sqrt（n）可以写。（看下数据范围，还是20）
：啊！我想到了nlogn的写法！！（看一下数据范围，这尼玛怎么还是20啊~~）
蒟蒻实在想不到更优秀的算法了，就先讲一下我们nlogn的“优秀”算法吧。
算法一：倍数筛筛筛
-
注意，我们之前在每个数都进行根号求因数的时候，其实重复了很多次。就是说你枚举根号n个数里面有很多数不是因数，没有什么用。我们要充分利用每一个数，减少不必要的枚举。所以，应该考虑每个数能对哪些数产生贡献。
-
如果当前数的因数个数确定了，那么它能产生的所有贡献都在是它的整数倍的数上。因此我们可以枚举当前数的所有倍数，把它的因数个数加到这个倍数的答案里。
-
那么我们如何知道当前数的因数个数呢？还要根号n求吗？其实不然，如果按照我们刚才说的筛法，我们对每个数再记录一下它被筛到的次数，那么当你递推到当前数的时候，你已经知道了它的因数个数，就是被筛的次数+1（1是它本身）。
-
复杂度怎么算？
每一个数枚举倍数，复杂度是n/i的，那么就是n/1+n/2+n/3+n/4+……+n/n，有同学说有点像n^2，别急。把n提出来，变成n*（1+1/2+1/3+1/4+…+1/n），（1+1/2+1/3+1/4+…+1/n）是调和级数，我们可以认为它是log的复杂度，因此本做法复杂度nlogn。
-
可是明明利用每个数那么充分了，怎么还是20分啊QAQ。说明我们的思路需要转化。（不过如果需要打表的同学，本算法算是最优秀的了）。
算法二：暴力出奇迹！分块打表
- 1e7内的答案我们可以在下面自己打出来，用上面的算法短时间内可以算出。不过1e7的数据肯定不能直接存入代码打表了，毕竟得1万行，100Mb左右（一位同学亲自试验）。
- 所以考虑分块打表，我们每隔5000个数，记录一个答案，这样的话，你对于1e7的数据，只需要存2000个数，是没问题的。然后块外面的数对答案的影响，直接暴力求没有问题吧，毕竟最多5000个数，你nsqrt（n）也是可以的。
- 60的高分喽
算法三：转化——三元组个数
- 先看一下d（p），它是不是可以转化成这样：∑（p%f==0），也就是f*k=p这样的二元组的个数，并且二元组有序。
- 然后∑d（p）是不是类似的，因为是连加的每一个p|i，所以其实是x * y * z=i这样的有序三元组的个数。
- 然后i从1~n，所以题目所求就是x * y * z <= n的有序三元组的个数。
- 不妨设x<=y<=z，那么x的范围在n^(1/3)内，y的范围则在sqrt（n/x）内。这样我们可以枚举了吧，枚举每一个x，然后枚举y，z有多少个自然可以求出来，累加到ans里。（注意使z>=y）。
- 因为刚才的是递增的，而三元组有6中排列，所以乘6.
- 但是有多计算的，比如说有两个数相同的三元组，只有三种排列，所以需要减去三倍。还有三个数相同的三元组，只有一种排列，所以减去五倍。
- 到此为止，本题做完了。是不是感觉一步一步推出来还挺有意思的？（考场快急哭了，有意思）。
Coding
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,x,y,z;ll ans; //wa的教训告诉我一定全部变量使用longlong
int main(){
freopen("divisor.in","r",stdin);
freopen("divisor.out","w",stdout);
scanf("%lld",&n);
ll l=pow(1.0*n,0.33333333)+1; //毒瘤题目卡精度，多加几个3
ll r;
for(x=1;x<=l;++x){
r=sqrt(1.0*(1.0*n/x))+1;
for(y=x;y<=r;++y){
z=n/(x*y);
while(x*y*z>n) z--;
if(z>=y){
ans+=1LL*(z-y+1)*6;
}
}
}
r=sqrt(1.0*n)+1;
for(x=1;x<=r;++x){
z=n/(x*x);
if(z>0){
if(z>=x) ans-=1LL*(z-1)*3;
else ans-=1LL*z*3;
}
}
for(x=1;x<=l;++x){
int temp=x*x*x;
if(temp<=n) ans-=5;
}
printf("%lld\n",ans);
return 0;
}T2和T3不太会啊，不是很可做
版权声明：本文为kgxw0430原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。