大神的世界

此題解答為

找出最小 N 使得 1 + 2 + ... + N >= k  且 1 + 2 + ... + N - k 為  2 的倍數

為什麼?

我們分 2 點討論

1. 為什麼 1 + 2 + ... + N - k 要為 2 的倍數？

假設 1 + 2 + ... + N - k = 2t   ,  t 為正整數

則將 t 拆成若干個 N 以下的數字，將這些數字取負號後，可使 1 + 2 + ... + N = k

例如 k = 12 

1 + 2 + 3 + 4 + 5 + 6 + 7 - 12 = 2 * 8

則 -1 + 2 + 3 + 4 + 5 + 6 - 7 = 12

因為正的變成負的會差 2 倍，因此 1 + 2 + ... + N - k 要為 2 的倍數

2. 為什麼這樣的 N 會最小 ?

若存在 N' < N 滿足題目要求

則 1 + 2 + ... + N' 必大於等於 k

且 1 + 2 + ... + N' - k 必為偶數

這與 N 為最小矛盾，因此不存在此 N'

( 因為 N 也符合上面性質，且 N 最小 )

寫的文謅謅...，自己舉幾個例子試看看就知道了

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
  int N, number;
  while(cin >> number){

    if(number<0)
      number = -number;
    
    N = sqrt(2*number);
    while(N*(N+1)<2*number)
      N++;

    if( (N*(N+1)/2 - number)%2 == 0 )
      cout << N << endl;
    else if(N%2)
      cout << N+2 << endl;
    else
      cout << N+1 << endl;
  }

  return 0;
}