[思维]HDU4473【Exam】题解
题目概述
令 $f(x)=\sum_{a=1}^{+\infty}\sum_{b=1}^{+\infty}[ab|x]$ ，求 $\sum_{i=1}^{n}f(i)$ 。
解题报告
emm……其实就是求 $\sum_{a=1}^{n}\sum_{b=1}^{n}\sum_{c=1}^{n}[abc\le n]$ ，这怎么搞呢？爆枚！
先枚举最小的 $a$ ，然后枚举较大的 $b$ ，可以证明复杂度是 $O(n^{2\over 3})$ ，我不会证……
示例程序
#include<cstdio>
using namespace std;
typedef long long LL;
LL n;int te;
inline LL Solve(LL n,LL ans=0){
for (LL a=1;a*a*a<=n;a++)
for (LL b=a;b*b*a<=n;b++){
LL c=n/(a*b);if (c<b) break;
a==b?ans+=(c-b)*3+1:ans+=(c-b)*6+3;
}return ans;
}
int main(){
freopen("program.in","r",stdin);freopen("program.out","w",stdout);
while (~scanf("%lld",&n)) printf("Case %d: %lld\n",++te,Solve(n));return 0;
}版权声明：本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处！
请不要发毫无意义或内容不文明的评论。与本文无关评论请发留言板！
