PAT B1087 有多少不同的值(C++)

PAT甲级目录 | PAT乙级目录

题目描述

当自然数 $n$ 依次取 1、2、3、……、N 时，算式 ⌊$n/2$⌋+⌊$n/3$⌋+⌊$n/5$⌋ 有多少个不同的值？（注：⌊$x$⌋ 为取整函数，表示不超过 $x$ 的最大自然数，即 $x$ 的整数部分。）

输入格式：

输入给出一个正整数 $N(2 \le N \le 10^4)$。

输出格式：

在一行中输出题面中算式取到的不同值的个数。

输入样例：

2017

输出样例：

1480

易错点

• 用 map 记录每个数出现的次数，键值等于1的时候说明该数第一次被记录
• 整数除法默认向下取整，所以不需要特殊调整

也许陌生的知识点

• map <int, int> m;
  • 功能：定义了一个键和值都为 int 型的 map 型变量，存放出现过的数并记录次数
    • 可以通过关键词名称索引访问对应值 m[key]++;
  • 需要头文件：map

代码示例：

# include <iostream>
# include <map>
using namespace std;
int main(){
  int n, cnt = 0;
  map <int, int> m;
  cin >> n;
  for(int i = 1; i <= n; i++){
    int key = i / 2 + i / 3 + i / 5;
    m[key]++;
    if(m[key] == 1) cnt++; //对新出现的数字计数
  }
  cout << cnt;
  return 0;
}