残りを最大にする除数を見つける方法は？

Question

nとkの2つの数字が与えられた場合、を最大にする,1 <= x <= kを見つける。

たとえば、n = 20およびk = 10の場合、残りの20％7 = 6が最大であるため、解はx = 7です。

int n, k; 
cin >> n >> k; 
int max = 0; 
for(int i = 1; i <= k; ++i) 
{ 
    int xx = n - (n/i) * i; // or int xx = n % i; 
    if(max < xx) 
    max = xx; 
} 
cout << max << endl; 

しかし、私の解決策はO(k)です：これまで

---

私のソリューションです。これにはもっと効率的な解決策がありますか？

Answer 1

漸進的に速くはありませんが、より速くはなく、単純に後退して、うまくできないことがわかったときに停止するだけです。

kがnより小さい（そうでない場合は、出力はk）。

int max = 0; 
for(int i = k; i > 0 ; --i) 
{ 
    int xx = n - (n/i) * i; // or int xx = n % i; 
    if(max < xx) 
    max = xx; 
    if (i < max) 
    break; // all remaining values will be smaller than max, so break out! 
} 
cout << max << endl; 

（これは、さらにこのように1つの条件文を排除し、限りi > maxとしてループのために行うことで改善することができるが、私はそれにそれがより明確にするには、この方法を書いた）

また、Gareyをチェックし、ジョンソンのコンピュータと難解な本は、これがNP完全ではないことを確認する（私はその本の中でこのように見えるいくつかの問題を覚えていると確信している）。私は、より良い解決策を考案しようと努力することに多大な努力をする前に、それをしています。

Answer 2

素敵な小さなパズル！

2つの簡単なケースから始めます。

n < k：任意x s.t. n < x <= kが解決します。

n = k：x = floor(k/2) + 1が解決されます。

私の試み。 n > kため

：

x = n 
while (x > k) { 
    x = ceil(n/2) 
} 

^----動作しませんでした。

x = ceil(float(n)/(floor(float(n)/k) + 1)) - 1

x = floor(float(n)/(floor(float(n)/k) + 1)) + 1

は^ ---- " 閉じる"（どんなことを意味します）が、動作しませんでした。

マイプライドは私が1.

ソリューションによって与えられ、最大k -bounded高調波を利用した最初のことを言及するために私に傾斜しています。他の回答と

インラインIは、単に現在の最大値（@TheGreatContiniの好意）によって制限、kよりn以下の高調波（@ColonelPanicの用語の礼儀）を確認します。これは両方の世界の中で最高です。成功した0〜10000000の間のランダムな整数でテストしました。

int maximalModulus(int n, int k) { 
    if (n < k) { 
     return n; 
    } 
    else if (n == k) { 
     return n % (k/2 + 1); 
    } 
    else { 
     int max = -1; 
     int i = (n/k) + 1; 
     int x = 1; 
     while (x > max + 1) { 
      x = (n/i) + 1; 
      if (n%x > max) { 
       max = n%x; 
      } 
      ++i; 
     } 
     return max; 
    } 
} 

性能試験： http://cpp.sh/72q6

出力例：

Average number of loops: 
bruteForce: 516 
theGreatContini: 242.8 
evgenyKluev: 2.28 
maximalModulus: 1.36 // My solution 

Answer 3

私は確かに間違っているんだけど、それはn < kかどうそれが依存している私には見えます。

つまり、n < kの場合はn%(n+1)となりますので、x = (n+1)となります。

まあ、他の一方で、あなたはj = kから開始し、それがnに等しくなるまでn%jを評価戻って、これx = jは、あなたが探しているとあなたが最大k段階でそれを買ってあげるものですすることができます...多すぎます、 それは...ですか？

Answer 4

波の手の周り

xがn次いでn%x=0の要因である場合ので、最大n%xを生成することができるnの要因であるxなし値。

したがって、xを考慮しないようにする手順は、nです。しかし、これは、xが要因であるかどうかを簡単に知りたいということを意味します。可能であれば素因数分解を簡単に行うことができます。

素因数分解を行う簡単な方法が知られているので、問題を解決するための「簡単な」方法はありません（私はあなたが単一の式を見つけるとは思わない、何らかの検索が必要になるだろう）。

しかし、素因数分解文献には素朴な検索に比べて素早く因子を得るための狡猾な方法があるため、おそらくあなたの質問に答えることができます。

Answer 5

k> nの場合、問題は簡単です（x = n + 1を取る）。

k < nについては、剰余n％xのグラフを考えてみてください。 n：n/2、n/3、n/4の高調波では、残りの部分はゼロになり、その後は跳躍し、次の高調波に向かって滑らかに減少します。

解は、kよりも右端の極大値です。数式x = n//((n//k)+1)+1（//は整数除算）です。

Answer 6

この問題は、与えられた範囲内で機能f(x)=n%xの最大値を見つけることと等価です。のは、この機能がどのようなものか見てみましょう：

それは我々がx=kで始まり、それが（x=max+1まで）どんな意味がありますしながらxを減少させる場合、我々はすぐに最大値を得ることができることは明らかです。また、この図は、xがsqrt(n)より大きい場合、xを順次減らす必要はないことを示しています。代わりに直前のローカル最大値に直ちにジャンプできます。

int maxmod(const int n, int k) 
{ 
    int max = 0; 

    while (k > max + 1 && k > 4.0 * std::sqrt(n)) 
    { 
     max = std::max(max, n % k); 
     k = std::min(k - 1, 1 + n/(1 + n/k)); 
    } 

    for (; k > max + 1; --k) 
     max = std::max(max, n % k); 

    return max; 
} 

マジック定数4.0最初の（高価な）ループの反復回数を減少させることによってパフォーマンスを改善することを可能にします。

最悪の時間の複雑さは、O（min（k、sqrt（n）））と見積もることができます。しかし、十分に大きい場合、kはこの見積もりはおそらくあまりにも悲観的です：我々はずっと早く最大値を見つけることができ、kがsqrt(n)よりかなり大きい場合、それを見つけるのに1回または2回の反復しか必要ありません。

私はnの異なる値のため、最悪の場合には必要とされている反復回数を決定するためにいくつかのテストをした：

n  max.iterations (both/loop1/loop2) 
10^1..10^2 11 2 11 
10^2..10^3 20 3 20 
10^3..10^4 42 5 42 
10^4..10^5 94 11 94 
10^5..10^6 196 23 196 
up to 10^7 379 43 379 
up to 10^8 722 83 722 
up to 10^9 1269 157 1269 

成長率は、O（SQRT（N））よりも著しく優れています。