「LGOJ」分类平均

题意

给定n和k(k≤100),将从 1 到 n 之间的所有正整数可以分为两类:A 类数可以被 k 整除(也就是说是k的倍数),而 B 类数不能。请输出这两类数的平均数,精确到小数点后 1 位,用空格隔开。

Link

题解

按照传统的暴力思想我们不难想出:

1
for(int i = k; i <= n; i+=k) ans += i

但是我们可以进行一下优化

设A的的个数有c个,则
$$
C=\lfloor \frac{n}{k}\rfloor
$$
所以我们可以得到A类的和是:
$$
k,1\times k,2\times k,…,C\times k
$$
化简一下一下(提取公因数)
$$
=\sum\limits_{n}^{i=1}i \times k
$$
我们在小学二年级学过等差数列的计算公式为:
$$
(首项+末项)\times 项数 \div 2
$$
于是乎:
$$
=(1+C)*C \div 2 \times k
$$
我们的A类数的和就求出来了!

那么B类数同理:
$$
B类数的和=总和-A类数的和
$$
最后除一下就好啦!

Code

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;

int main(){
int n,k;
scanf("%d%d",&n,&k);
int C=floor(n/k);
double A=(1+C)*C/2*k;
double B=(1+n)*n/2-A;
printf("%.1f %.1f",A/C,B/(n-C));
return 0;
}
0%