题目内容

P1403

大意:令 \tau(x) 表示正整数 x 的正约数个数,求 \sum_{i=1}^n\tau(x)

解题思路

暴力:枚举每个数的所有因数个数然后加起来即可,时间复杂度 O(n\sqrt n),光荣 T 三个点

先放公式:

\sum_{i=1}^n\tau(x)=\sum_{i=1}^n\frac n i

原理:在区间 [1,n] 中,有 1 这个约数的数有 n/1 个,有 2 这个约数的数有 n/2 个,… 有 i 为约数的数有 n/i 个,所以跑一次 O(n) 统计答案即可。

这代码真尼玛短

#include <cstdio>

int main()
{
    int n,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        ans+=n/i;
    printf("%d\n",ans);
    return 0;
}
最后修改日期:2020年2月16日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。