牛客练习赛77

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

输入

输出

备注

数据范围：\(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

输出

示例2

输入

5 3

输出

备注

数据范围：\(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

输入

输出

备注:

数据范围：\(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;
}