在[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(地板(Z/X)−装天花板(Y/X) + 1;

0)

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

Answer 2

下面应该可以做到(经过一些更多的测试)。

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

解释

1. 求a/m和b/m之间m的倍数
2. 如果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来得到下一个倍数所以我们不需要从第一个值遍历到最后一个值来检查value是否为倍数，我们只需要找到第一个倍数那么到达最后一个值所需要的步数就是M加a得到的B

Answer 4

效果很好。

int multiples = 0;
    for(int i = x; i<=y; i++){
     if(i%z==0)
      multiples++;
    }

只要是y>x，如果不总是为真，只需添加一个额外的if语句来检查是y>x还是x>y。:)