「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个,则

所以我们可以得到A类的和是:

化简一下一下(提取公因数)

我们在小学二年级学过等差数列的计算公式为:

于是乎:

我们的A类数的和就求出来了!

那么B类数同理:

最后除一下就好啦!

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%