首页 > 小G的sum
开通博客写题解
头像 ujnxiaochen
发表于 2021-02-26 23:07:24
C、小G的约数前置知识：整除分块https://blog.csdn.net/weixin_45419138/article/details/103446724G(n)为约数和的和最大值n=50000,可以先用朴素方法把F(N)表打出来，即求出每一个数的因子和，复杂度为O(nsqrt(n))发现n=5 展开全文
去ta的博客 赞 (10) 回复(0) 收起
头像 EMT_TPYQ
发表于 2021-03-01 09:24:27
经典的，我们容斥，此时可以简单理解成将值域划分若干段，每个长度的贡献乘在一起，最后设用了 段，则乘以 简而言之，设 ，则答案可以描述为 设 ，那么我们只需要计算 ，设 的复合逆为 由拓展拉格朗日反演： 解 则只需要考虑如下方程： 复杂度 ，不过常数会十分感人就是了。 不知道为什么牛客的 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 sunrise__sunrise
发表于 2021-02-27 19:00:54
A、小G的sum 对于每个数，最小的约数是1，最大的约数是它本身。那么使用等差数列求合即可。 void solve() { n = read(); ll ans = n + (1 + n) * n / 2; print(ans); } B、小G的GCD 对于单个，很容易发现可 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 qingshan_12
发表于 2021-02-26 22:16:01
链接：https://ac.nowcoder.com/acm/contest/11160/B 小G给你两个数n,k我们定义F(x)为i从1~x i%k==0的i的和现在希望你求出sum i=1..n F(i) 假设 a 满足 % k == 0 的数之和，x 能满足的话， 从定义来看，那么大于a，小于 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 TheOnlyMan
发表于 2021-02-26 22:06:46
一个数的最小约数肯定是1，最大约数就是它自己。 那么要求最小约数的和加最大约数的和，可以发现最小约数和为n(是n1)。最大约数和便是1+...+n(从1加到n),采用等差公式直接求得n(n+1)/2,两者相加便可以了。记得开long long,不然数据会溢出。 #include<iostrea 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 CoolGuang!
发表于 2021-02-26 22:50:20
这是个比较简单的整除分块吧.. 但是我不是数论选手，所以就先去写D了.. 这个题还是比较裸的，如果知道约数和的写法的话 首先考虑直接求约数和不太现实，所以我们可以枚举约数，求约数对答案的贡献。 首先1~n所有的约数最大值不可能超过n 所以我们可以考虑所有的约数，用f(i)表示i的倍数在n之前有多少个 展开全文
去ta的博客 赞 (2) 回复(2) 收起
头像 qingshan_12
发表于 2021-02-26 22:06:57
链接：https://ac.nowcoder.com/acm/contest/11160/A给定一个n, 定义mind(n)为n最小的约数，maxd(n)为n最大的约数求sum i=1..n mind(i) + sum i=1..n maxd(i)任意一个数的最小约数是1，最大约数是本身。所以求1- 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 あおいSakura
发表于 2021-03-08 21:50:53
小G的sum 题目链接：nowcoder 218396 到主站看：https://blog.csdn.net/weixin_43346722/article/details/114551682 题目大意 求 1~n 中每个数最小的约数和最大的约数的和。 思路 大家都知道，一个数最小的约数是 ，最大的 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 东溪看水
发表于 2021-03-01 10:18:20
题目 给定一个 n, 定义 mind(n) 为 n 最小的约数，maxd(n) 为 n 最大的约数求 。 解题思路 一个数的最小的约数是 1，最大的约数是它本身。 C++代码 #include<iostream> using namespace std; int main(){ 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 chstor
发表于 2021-03-11 20:43:03
A、小G的sum 题目分析： 代码如下： #include<iostream> using namespace std; int main(){ long long n; cin >> n; cout<<n+n*(n+1)/2; 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”