为什么是sum*2-t*t呢?

#include<cmath>
#include<cstdio>
#include<cstring>
usingnamespacestd;
typedef longlong ll;
intmain() {
    intq; scanf("%d", &q);
    while(q--) {
        intx; scanf("%d", &x);
        ll ans=0;
        intt=sqrt(x+1);
        for(inti=1; i<=t; ++i) ans+=(x/i);
        printf("%lld\n", ans*2-t*t);
    }
    return0;
}
这里的这句没太看懂,求dalao指点一下
全部评论
1~n 约数的个数的和实际就是看 1~n 在这些数中出现过多少次,例如 1是1~n每个数的因数,所以对1这个因数来说,出现了n/1次,以此类推; 发现答案 1/n+2/n+3/n+……+n/n 其实就是函数 y=1/x 在1~n 上的离散和,因为函数关于直线 y=x 对称,求 1~√n 离散合再减去重复的地方即可;
4 回复 分享
发布于 2018-08-25 09:50
乘以2是因为一个数的因子有i,则x/i也是x的因子,所以算两个。减去每个数i都有i-1个重复计算了,再减去自己跟自己相乘的情况,合起来减去t*t
3 回复 分享
发布于 2018-08-25 11:34
这个算法有问题.AC代码给出的结果应该是20,打个草稿也应该是20但是这个算法给出的答案是19有问题
点赞 回复 分享
发布于 2018-08-26 12:05

相关推荐

10-22 15:25
门头沟学院 C++
种花网友小松:求求你别发了,我几乎都快嫉妒得疯了,倒在床上蒙住被子就开始抱着枕头尖叫流泪,嘴里一边喊着卧槽卧槽,一边又忍着,我边发边哭,打字的手都是抖的,后来我的手抖得越来越厉害,从心头涌起的思想、情怀和梦想,这份歆羡和悔恨交织在一起,我的笑还挂在脸上,可是眼泪一下子就掉下来了。求你了别发了,我生活再难再穷我都不会觉得难过,只有你们发这种东西的时候,我的心里像被刀割一样的痛,打着字泪水就忍不住的往下流。
我的求职进度条
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务