13th.Feb.2019

13th.Feb.2019

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; //毒瘤题目卡精度，多加几个3ll 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("%lldn",ans);return 0;
}

T2和T3不太会啊，不是很可做

 posted on 2019-02-14 20:32 kgxpbqbyt 阅读( ...) 评论( ...) 编辑 收藏