指定された範囲 x、y。間にあるすべての数値をカウントする必要があり、n で割り切れます。
これを行う簡単な方法は、範囲全体をループすることです。
for(int i=x;i<=y;i++) if(i%n ==0) counter++;
カウンターは答えを保持します。
しかし、これは大きな範囲では非常に遅くなります。たとえば、 x=0 と y=3,000,000,000 です。
反復回数を減らし、このコードを最適化して速度を上げるために使用できる関係があると確信しています。探しましたがわかりませんでした。誰でもそれを手伝ってくれませんか。
本当にありがとう。
これは動作します: (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 および 0 < d の場合、型の範囲内の s および e の任意の値に対して機能します。
e = e < 0 ? (e+1)/d - 1 : e/d;
s = s <= 0 ? s/d - 1 : (s-1)/d;
return e-s;
基本的に、最初の 2 つのステートメントは と同等でe = e/dありs = (s-1)/d、0 ではなく -infinity に丸めるように除算が変更されています (-1/10 が 0 ではなく -1 になるように)。
(floor)(high/d) - (floor)(low/d) - (high%d==0)
説明：
0 から a までの d で割り切れる a/d 数があります。(d!=0)
したがって、 (floor)(high/d) - (floor)(low/d) は、範囲 (low,high] で割り切れる数値を返します (この範囲には、low が除外され、high が含まれることに注意してください)。
範囲から高を削除するには、単に減算します (high%d==0)
float には fmodf を使用します。
この実装のみが機能します（[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;
}
public int myfunc(int low, int high, int test) {
int count = 0;
if(low % test == 0)
count++;
count +=(high-low)/test;
return count;
}
私はあなたがこれを行うことができると確信しています：
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
すべての数字を繰り返すのではなく、試すことができます
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;
}
除数の倍数のみを使用します。これで、繰り返し除算 (遅い) を行っているのではなく、繰り返し乗算 (高速) を行っています。
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;
}
n で割り切れる x と y (x と y の両方が範囲に含まれる) の間の整数の数のカウントを要求しました。ループする必要はなく、答えを計算するのに 2 つの除算だけが必要です。簡単な例を考えてみましょう: 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 です。いくつかの方法で計算できます。両端の商を取り、それらを引きます: 28 - 14 = 14. または、2 つの端点の差を取り、除数で割り、1 を追加します: 196 - 105 = 91、91 / 7 = 13、13 + 1 = 14. ただし、端点の 1 つが除数で割り切れる場合は注意してください。詳細はお任せします。プログラムも書きます。
以下のアルゴリズムに関するコメントを親切に提供してください: 範囲が [R1,R2] で、分割される数が n であるとします。
n で割り切れる R1 から始まる最小の数を見つけます。小さい数と呼びます。
n で割り切れる R2 から始まる最大の数を見つけます。大と呼んでください。
割り切れる数の合計= (大小)/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);
}
ええと、私は大学の教授ではないので、驚くような公式はありませんが、私の知る限り、そのような数値のリストをチェックする唯一の方法は、それらを反復処理することです。最終的には、割り切れるかどうかを確認するために変数を評価する必要があります。アルゴリズムを最適化する方法があります。最初に数値を並べ替えます。これは最初はコストがかかりますが、数値を確認する必要がある場合は、はるかに高速になります。
ソート アルゴリズムを検討することをお勧めします。私が使用するのはバブル ソートで、Google でかなり出てくるでしょう。
並べ替えでできることについては、数値を倍数のリストに並べ替えることができます。たとえば、2 4 6 8 はすべて 2 の倍数なので、基本的にリストの最初のものをチェックでき、残りはすぐにわかります。割り切れる
私の2セントを提供するだけで、これを行うためのはるかに効率的な方法があるかもしれないことに注意してください