莫比乌斯反演准备

前置技能
d = 1 n [ n / d ] \sum_{d=1}^n{[n/d]} d=1n[n/d](下取整函数)
n<1e14;
对于[n/d] 的每个取值,对应d的范围一定是一个区间,枚举[n/d]的取值即可。

#include<cstdio>
#include<iostream>

using namespace std;
typedef long long LL;

int main(){
   LL n=0;
   scanf("%lld",&n);
   LL ans=0;
   for (LL i=1;i<=n;i++){
   	LL t=n/i,j=n/t;
   	ans+=(j-i+1)*t;//(j-i+1)为区间
	   i=j; 
   }	
   printf("%lld\n",ans);
	return 0;
} 

题目
i = 1 n i = 1 m d ( i j ) \sum_{i=1}^n\sum_{i=1}^md(ij) i=1ni=1md(ij)

全部评论

相关推荐

05-14 20:34
门头沟学院 Java
窝补药贝八股:管他们,乱说,反正又不去,直接说680
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务