小G的约数

小G的sum

https://ac.nowcoder.com/acm/contest/11160/A

这是个比较简单的整除分块吧..

但是我不是数论选手,所以就先去写D了..

这个题还是比较裸的,如果知道约数和的写法的话

首先考虑直接求约数和不太现实,所以我们可以枚举约数,求约数对答案的贡献。

首先1~n所有的约数最大值不可能超过n

所以我们可以考虑所有的约数,用f(i)表示i的倍数在n之前有多少个,那么有公式:

所以自然有下面的求和公式:

该和可以以的复杂度求和,所谓整除分块,具体证明不提(网上一搜一片),如果你和我一样对于数学不敏感,那么就直接记住:

而且取值最多有 种,所以复杂度稳定在根号下

剩下的就套一下就好了,注意计算时涉及到等差数列求和:

/*** keep hungry and calm CoolGuang!  ***/
//#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e6+700;
const int M = 1e6+8;
const ll mod= 1e6+7;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
ll get(ll x){
    ll ans = 0;
    for(int i=1;i<=x;i++){
        int r = (x/(x/i));
        ans += (r-i+1ll)*(x/i)*(x+i)/2;
        i = r;
    }
    return ans;
}
int main(){
    read(n);
    printf("%lld\n",get(get(n)));
    return 0;
}

全部评论
第28行应该是ans += (r-i+1ll)*(x/i)*(r+i)/2;吧
4 回复 分享
发布于 2021-02-27 10:46
i'的最大值应该是N/(N/i)吧
1 回复 分享
发布于 2021-02-27 16:00

相关推荐

07-24 19:01
门头沟学院 Java
后天笔试,又要开始做题了
Sairus:明天10:00笔试
投递京东等公司10个岗位
点赞 评论 收藏
分享
07-25 10:39
门头沟学院 Java
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

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