5

给定范围 x, y。我需要计算两者之间的所有数字并且可以被n整除。

我知道做到这一点的简单方法是在整个范围内循环

for(int i=x;i<=y;i++) if(i%n ==0) counter++;

柜台持有答案。

但这对于大范围来说非常缓慢。例如 x=0 和 y=3,000,000,000。

我确信有一些关系可以用来减少迭代次数并优化此代码以提高速度。我搜索了但我找不到它。任何人都可以帮助我吗？

非常感谢。

4

10 回答 10

7

这有效：(e+1 - s) / d + (e%d < (s+d-1)%d). （它使用 C 语义和整数算术并假设开始是非负的。s 是开始值，e 是结束值 [包括]，d 是除数。）

更新：更好的解决方案是e/d - (s-1)/d. 这是受 User448810 启发的。这要求 s 是积极的；处理零或负 s（或 e）需要将截断调整到零（对于这个问题，我们希望向负无穷大）。

负值更新：以下适用于 s 和 e 在其类型范围内的任何值，前提是 s <= e 和 0 < d：

e = e <  0 ? (e+1)/d - 1 : e/d;
s = s <= 0 ? s/d - 1 : (s-1)/d;
return e-s;

本质上，前两个语句等价于除法，e = e/d并且s = (s-1)/d除法被修改为朝 -infinity 舍入而不是朝零舍入（因此 -1/10 产生 -1 而不是 0）。

于 2012-08-04T01:13:17.657 回答
2 
(floor)(high/d) - (floor)(low/d) - (high%d==0)

解释：

从 0 到 a 有可被 d 整除的 a/d 数。(d!=0)

因此 (floor)(high/d) - (floor)(low/d) 将给出在 (low,high] 范围内可整除的数字（注意，不包括低，高包括在此范围内）

现在要从范围中删除高点，只需减去 (high%d==0)

对浮点数使用 fmodf。

于 2014-06-20T14:28:32.740 回答
0

只有这个实现对我有用（[0..2kkk] 中的 A、B；[1..2kkk] 中的 K）：

function solution(A, B, K) {
    if(B < K) return A === 0 ? 1 : 0;
    if(A === B) return A % K === 0 ? 1 : 0;

    var pre = A === 0 ? 2 : 1;
    var min = A < K ? K : A + A % K;
    var max = B - B % K;

    return (max - min) / K + pre;
}
于 2014-10-27T13:12:19.653 回答
-1

我很确定你可以这样做：

public static int numDivisible(int low, int high, int test) {
    return (high-low)/test;
}

你去吧。一个恒定时间的解决方案。由于您不需要确切知道哪些数字是可整除的，因此您无需费心遍历所有数字。

编辑：根据@Chaser324 将其更改为以下内容。

public static float numDivisible(float low, float high, float test) {
    return Math.ceil((high-low)/test);
}

编辑：一个小错字，即，text改为test

于 2012-08-04T00:55:05.383 回答
-1

而不是迭代每个数字，您可以尝试

public int test(int floor, int ceil, int n) {
    int a = (floor / n) + 1;
    int counter = 0;
    while (a * n <= ceil) {
        counter++;
        a++;
    }
    return counter;
}

并且只使用除数的倍数。现在您不是在重复除法（慢），而是在重复乘法（更快）。

于 2012-08-04T00:58:15.823 回答
-1 
public static int solution(int low,int high, int n) {
    boolean h0=high%n==0;
    boolean l0=low%n==0;

    int k1=l0?low/n:(low+n-low%n)/n;
    int k2=h0?high/n:(high+n-high%n)/n;

    //                 |-----------|
    // ---------------k1----------k2---------------

    if(k2*n>high) k2--;

    return k2-k1+1;

}
于 2012-08-04T01:58:10.710 回答
-1

您要求计算 x 和 y（x 和 y 都包含在范围内）之间可被 n 整除的整数个数。不需要任何循环，只需要两次除法即可计算答案。让我们考虑一个简单的例子：对于 100 到 200 的范围，有多少个整数可以被 7 整除？

从范围的低端开始：100 / 7 = 14，余数为 2。现在除数 7 减去余数 2 为 5，因此可被 7 整除的最小数为 100 + 5 = 105。

现在转到范围的高端：200 / 7 = 28，余数为 4，因此范围上可被 7 整除的最大数是 200 - 4 = 196。

因此，范围内能被 7 整除的数字是 105、112、119、126、133、140、147、154、161、168、175、182、189 和 196。其中有 14 个，你可以通过几种方式计算。取两端的商并减去它们：28 - 14 = 14。或者取两个端点的差，除以除数，然后加1：196 - 105 = 91, 91 / 7 = 13, 13 + 1 = 14. 但是当端点之一可以被除数整除时要小心；我将把它留给你来制定细节，并编写程序。

于 2012-08-04T01:58:50.217 回答
-1

请提供以下算法评论：假设范围是[R1，R2]，要划分的数字是n。

找到从 R1 开始可被 n 整除的最小数。称其为小数。

找到从 R2 开始可被 n 整除的最大数。称其为大。

可整除的总数=（大-小）/n + 1。

最坏的情况仍然是 O(n)，但对于 R1 和 R2 之间的巨大差异可能是有效的。希望我已经涵盖了所有情况。请建议。

int numofDivisible(int R1, int R2, int n) {

int small = R1, large= R2;

if ((R1 > R2) || (n==0)) return 0;

if (R1 == R2) {
    if (R1 % n == 0) 
        return 1;
    else 
        return 0;
}

while(small <= R2){

     if(small % n == 0)
         break;

      ++small;
}

if (small > R2)
    return 0;


while (large > small) {

    if (large % n == 0)
       break;

    --large;
}

if (large == small)
   return 1;

return ((large-small)/n + 1);

}
于 2012-08-04T02:03:27.120 回答
-1 
 public int myfunc(int low, int high, int test) {   
    int count = 0;
    if(low % test == 0)
       count++;
    count +=(high-low)/test;
    return count;
 }
于 2014-01-18T10:44:48.093 回答
-2

好吧，我不是大学教授，所以我没有给你一些惊人的公式，但据我所知，检查这样的数字列表的唯一方法是迭代它们，最后你会必须评估变量以检查它是否可整，现在有一种方法可以优化您的算法，首先对数字进行排序！这最初会很昂贵，但是任何后续检查数字的需要都会快得多，

我建议查看排序算法，我会使用冒泡排序，它会在谷歌上出现很多。

至于你可以用排序做什么，你可以将数字排序到倍数列表中，例如 2 4 6 8 都是 2 的倍数，所以你基本上可以检查列表中的第一个，其余的会立即知道也是可分的

请记住，这样做可能有更有效的方法，只需提供我的 2 美分

于 2012-08-04T00:51:35.277 回答