【DidaOJ】[1133]感恩节KK专场——2015年的第一场雪

问题描述

问题分析

核心算法：

对于正整数 n 和 k，从 1 到 n 中可以被 k 整除的数的个数，就是：

$$ \lfloor \dfrac{n}{k} \rfloor $$

也就是说，只需要用 n 除以 k，然后取整数部分即可。

因此区间 [a, b] 中能被 k 整除的个数，可以使用这个公式：

$$ \lfloor \dfrac{b}{k} \rfloor - \lfloor \dfrac{a-1}{k} \rfloor $$

但是具体实现的时候，由于C++默认的整数除法逻辑，对于结果是负数的情况会不太符合预期，因此需要自己处理结果是负数的情况。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>  

typedef long long ll;  
  
bool is_same_sign(ll a, ll b)  
{  
    return (a ^ b) >= 0;  
}  
  
ll get_floor_div(ll a, ll b)  
{  
    if (b == 0)  
    {  
        return 0; // Handle division by zero  
    }  
    ll res = a / b;  
    if (!is_same_sign(a, b) && a % b != 0)  
    {  
        res--;  
    }  
    return res;  
}  
  
ll get_div_number(ll k, ll x, ll y)  
{  
    if (k == 0)  
    {  
        return 0;  
    }  
    if (k < 0)  
    {  
        k = -k;  
    }  
    return get_floor_div(y, k) - get_floor_div(x - 1, k);  
}  
  
int main()  
{  
    int T;  
    scanf("%d", &T);  
    while (T--)  
    {  
        int k, x, y;  
        scanf("%d %d %d", &k, &x, &y);  
        printf("%lld\n", get_div_number(k, x, y));  
    }  
    return 0;  
}

题目地址：感恩节KK专场——2015年的第一场雪 - 问题详情 - 题目 - DidaOJ