查找范围 [Java] 之间的数字的倍数

Question

我们得到了一个范围 A<=B 和一个数字 M。我们必须找到给定范围内有多少 M 的倍数。

我的解决方案：

import java.util.Scanner;

class ABC {
public static void main(String args[] ) throws Exception {

    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    for (int i = 0; i < N; i++) {
        long A = sc.nextLong();
        long B = sc.nextLong();
        long M = sc.nextLong();

        int res = 0;
        while(A<=B)
        {
            if(A%M==0)res++;
            A++;
        }
        System.out.println(res+"");
    }
    }
}

现在这不是很有效。请告诉我如何在最短的时间内解决这个问题。

Answer 1

使n1*M≥A的最小整数n1为n1=ceil(A/M)，使n2*M≤B的最大整数n2为n2=floor(B/M ). n1 和 n2 之间的整数个数为 max_of(n2−n1+1 ; 0).

结合以上我们得到答案：

max_of(floor(Z/X)−ceil(Y/X)+1 ; 0)

这是竞争性编程中的标准问题:D

Answer 2

下面应该这样做（经过更多测试）。

int r = (b/m - a/m) + (a % m == 0 ? 1 : 0);

说明

求 a/m 和 b/m

m

如果a是m的倍数再加一个(a % m == 0 ? 1 : 0)

PoC小例子

public static void main(String[] args) throws Exception {
    int[][] pairs = {{10, 24}, {10, 25}, {11, 24}, {11, 25}, {10, 27}};
    int m = 5;
    for (int[] pair : pairs) {
        int a = pair[0];
        int b = pair[1];
        int r = (b/m - a/m) + (a % m == 0 ? 1 : 0);
        System.out.printf("a: %d  b: %d  result = %d  ", a, b, r);
        for (int i = a; i <= b; i++) {
            if (i % m == 0) {
                System.out.print(" " + i);
            }
        }
        System.out.println("");
    }
}

输出

a: 10  b: 24  result = 3   10 15 20
a: 10  b: 25  result = 4   10 15 20 25
a: 11  b: 24  result = 2   15 20
a: 11  b: 25  result = 3   15 20 25
a: 10  b: 27  result = 4   10 15 20 25

Answer 3

试试这个代码：

long A = sc.nextLong();
    long B = sc.nextLong();
    long M = sc.nextLong();

    if (M > A) {
        A = M;
    }
    if(M > B){
        System.out.println("0");
        return;
    }
    System.out.println(  (((B-A)/M)+1) + "");

解释：

如果 2 是第一个倍数而不是我们不需要检查 3 的倍数，我们必须加 2 以获得下一个倍数所以我们不需要从第一个值遍历到最后一个值并检查值是否是倍数，我们只是需要找到第一个倍数，而不是达到最后一个数字所需的步数意味着我们的 B 通过将 M 添加到 A.

查找范围 [Java] 之间的数字的倍数

Finding Multiples of a number between a range [Java]

java

performance

numbers