查找某个范围内某个数的倍数[Java]

jjjwad0x  于 2022-12-17  发布在  Java
关注(0)|答案(4)|浏览(197)

我们已经给出了一个值域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+"");
    }
    }
}

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

sulc1iza

sulc1iza1#

最小整数n1使得n1M ≥ A为n1=ceil(A/M),最大整数n2使得n2M ≤ B为n2=floor(B/M),n1和n2之间的整数个数为max_of(n2−n1+1 ; 0)。
综合以上几点,我们得出了答案:
(下限(Z/X)-上限(Y/X)+1)的最大值; 0)
这是竞争性编程中的标准问题:D

x7rlezfr

x7rlezfr2#

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

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

解说
1.求出a/mb/m之间的倍数m
1.如果am倍数,则再加上一个(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
uhry853o

uhry853o3#

请尝试以下代码:

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以得到下一个倍数,因此我们不需要从第一个值遍历到最后一个值并检查值是否是倍数,我们只需要找到第一个倍数,然后通过将M加到A,到达最后一个数所需的步数意味着我们的B。

snz8szmq

snz8szmq4#

这个很好用。

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

只要y〉x,如果不总是这样,只需添加一个额外的if语句,检查y〉x还是x〉y。

相关问题