SH1034 倍数统计
小于 1 分钟
SH1034 倍数统计
【算法】 数学、整除
【C++】 整数除法、数学公式
【难度】 入门
一、题目简述
给定整数 与正整数 ,求出在 到 之间(包含 与 )有多少整数是 的倍数。
二、解题思路
不需要逐个枚举( 可能很大)。直接用数学公式:
区间 中 的倍数个数 =
原理: 是 中 的倍数个数, 是 中 的倍数个数,相减即得 中的个数。
手动模拟:
- (1~6 中 5 的倍数:5)
- (1~3 中没有 5 的倍数)
- 结果: ✅
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, c;
cin >> a >> b >> c;
int ans = b / c - (a - 1) / c;
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间:,纯数学计算。
- 空间:。
五、易错点
注意是 (a-1)/c 不是 a/c。因为要算的是 的倍数个数,而非 的。
