牛客练习赛27 B 手办

题意

给你一个n

定义f(x)为a*b整除x的(a,b)个数

求f(1)+f(2)+…+f(n)

废话

好久没有更博客了。。

其实都是写了没有发出来。。

你问我为什么不发出来？

因为写得都很简略。。类似题表一样，记录一下自己做了哪些题罢了。。

或许等我退役的时候会压成一个文件发出来吧。。

话说csdn连手写的makedown怎么都不支持啊。。还要在上面找功能。。

真麻烦

题解

这题，很容易搞着搞着就会要求约数和。。

然后分块套分块，是 n 3 4 n^{\frac{3}{4}} n43​,过不去

如果要写杜教筛的话，想要做到 n 2 3 n^{\frac{2}{3}} n32​，要处理到 1 0 8 10^8 108，也不支持。。

然后就变成毒瘤题了。。

但其实换一个思路，就不毒瘤了。。

我们可以把f(x)看作 a × b × c = x a\times{b}\times{c}={x} a×b×c=x的个数

那么答案要求的就是 a × b × c &lt; = x a\times{b}\times{c}&lt;={x} a×b×c<=x

规定一下顺序。。

排列一下就可以算出来了。。

复杂度并不会证

但肯定比前面那两个快。。

#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;typedef long long LL;const LL MOD=2333;LL dec (LL x,LL y){x=x-y;if (x<0) x=x+MOD;return x;}LL add (LL x,LL y){x=x+y;if (x>=MOD) x=x-MOD;return x;}LL mul (LL x,LL y){return x*y%MOD;}int main(){LL n;scanf("%lld",&n);LL ans=0;for (LL u=1;u*u*u<=n;u++){ans=add(ans,1);ans=add(ans,mul(n/u/u-u,3));for (LL i=u+1;i*u*i<=n;i++){ans=add(ans,3);ans=add(ans,mul(n/i/u-i,6));}}printf("%lld\n",ans);return 0;}

如果觉得《牛客练习赛27 B 手办》对你有帮助，请点赞、收藏，并留下你的观点哦！