当自然数$n$依次取$1,2,3,…,N$时，算式$⌊n/2⌋+⌊n/3⌋+⌊n/5⌋$有多少个不同的值？（注：$⌊x⌋$为取整函数，表示不超过$x$的最大自然数，即$x$的整数部分。）
输入格式
输入给出一个正整数$N(2≤N≤10^4)$。
输出格式
在一行中输出题面中算式取到的不同值的个数。
输入样例
1 | 2017 |
输出样例
1 | 1480 |
分析
正常情况下，随着$n$增加1，算式会增加1或者0；当$n$是6/10/15的整数倍的时候，算式会增加2（缺失1个数字）；当$n$是30的整数倍的时候，算式会增加3（缺失2个数字）。
因此要计算不同值的个数，只需要计算最后一个数字代入的结果+1（+1是因为有0的存在），再减去缺失的数字个数即可（30的整数倍不减反加是因为30是6,10,15的最小公倍数，已经被减了3次，因此需要加1次来弥补）。
$ans = \frac{N}{2}+\frac{N}{3}+\frac{N}{5}+1-\frac{N}{6}-\frac{N}{10}-\frac{N}{15}+\frac{N}{30}$
AC代码
1 | |
2 | using namespace std; |
3 | int main() |
4 | { |
5 | int n; |
6 | scanf("%d",&n); |
7 | printf("%d",n/2+n/3+n/5+1-n/6-n/10-n/15+n/30); |
8 | return 0; |
9 | } |
