A-小G的sum
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
给定一个\(n\), 定义\(mind(n)\)为\(n\)最小的约数，\(maxd(n)\)为\(n\)最大的约数
求\(\sum_{i=1}^n mind(i) + \sum_{i=1}^n maxd(i)\)
输入描述
给定的\(n\)
输出描述
输出要求的答案
示例1
输入
5
输出
20
备注
数据范围：\(1 \leqslant n \leqslant 1e9\)
PZ's Solution
1.一个数字\(x\)，它的最小约数即\(mind(x)=1\)，它的最大约数即\(maxd(x)=x\)；
2.则\(\sum_{i=1}^x mind(i) + \sum_{i=1}^x maxd(i)=x+\frac{x(x+1)}{2}\)
- TAG：数学；约数
PZ.cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int main() {
scanf("%d", &n);
printf("%lld", n + 1ll*(n + 1)*n / 2);
return 0;
}
B-小G的GCD
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
小G给你两个数\(n,k\)
我们定义\(F(x)\)为\(i\)从\(1\sim x\)，$ i%k==0\(的\)i\(的和
现在希望你求出\)\sum_{i=1}^n F(i)$
输入描述
给定两个数\(n，k\)
输出描述
要求输出的答案
示例1
输入
2 1
输出
4
示例2
输入
5 3
输出
9
备注
数据范围：\(1 \leqslant n,k \leqslant 1e6\)
PZ's Solution
直接使用前缀和累加求出\(F(i)\)即可；
- TAG：数学
PZ.cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,k;
long long ans,f[1000005];
int main(){
scanf("%d %d",&n,&k);
for(int i=1;i<=n;++i){
if(i%k==0) f[i]=f[i-1]+i;
else f[i]=f[i-1];
ans+=f[i];
}
printf("%lld",ans);
return 0;
}
C-小G的约数
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
小G定义了两个函数
\(F(n)\)为\(n\)的约数和，
\(G(n)\)为\(\sum_{i=1}^nF(i)\)，
小G想知道\(G(G(n))\)等于多少
输入描述
小G会给你一个\(n\)
输出描述
输出一个数\(G(G(n))\)即可
示例1
输入
5
输出
371
备注:
数据范围：\(1 \leqslant n \leqslant 5e4\)
PZ's Solution
1.由于\(G(n)=\sum_{i=1}^nF(i)\)，可得\(G(G(n))=G(\sum_{i=1}^nF(i))=\sum_{i=1}^{\sum_{j=1}^nF(j)}F(i)\)；
2.也就是，本题实际上是要求 \([1,n]\)的约数和 的约数和；
3.对于\([1,n]\)的约数和：
考虑对于每个约数\(x\)，在\([1,n]\)中，\(x\)是约数的次数为\(\lfloor\frac{n}{x}\rfloor\)，则约数\(x\)的贡献即为\(\lfloor\frac{n}{x}\rfloor \times x\)；
可以得出代码：
int ans=0; //ans为[1,n]的约数和，即G[n]
for(int i=1;i<=n;++i){
ans+=n/i*i;
}
但由于本题\(n\)的范围很大，\(O(G(n))\)的时间复杂度必然不能满足要求；
4.发现每个约数\(x\)有贡献\(\lfloor\frac{n}{x}\rfloor\)，对于多个约数\(y\)，很可能会出现\(\lfloor\frac{n}{x}\rfloor=\lfloor\frac{n}{y}\rfloor\)，这时考虑整除分块；
关于整除分块，可以看
的整除分块（数论分块）
5.设每个\(\lfloor\frac{n}{i}\rfloor\)相同的块的左端点为\(l\)，则右端点可得为\(r=\lfloor\frac{n}{\frac{n}{l}}\rfloor\)，
则区间\([l,r]\)的贡献为\(\lfloor\frac{n}{l}\rfloor \times \frac{(l+r)(r-l+1)}{2}\)，且时间复杂度降为\(O(\sqrt{G(n)})\)；
- TAG：整除分块；约数；数论
PZ.cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
int N;
ll Solve(int n){
ll ans=0;
for(ll l=1,r;l<=n;l=r+1){
r=n/(n/l);
ans+=(n/l)*(l+r)*(r-l+1)/2;
}
return ans;
}
int main(){
scanf("%d",&N);
printf("%lld",Solve(Solve(N)));
return 0;
}