menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[思维]HDU4473【Exam】题解
apps HDU
local_offer 查看标签
comment 0 条评论

题目概述

令 $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协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up