ACM: 138 – Street Numbers

這題寫出來超開心！

要找到n, k，使得1 + 2 + 3 + … + (k-1) = (k+1) + (k+2) + … + n。這題是no input，要傳回前10對n, k。題目已經給出前2對，第一對是(6, 8)，因為1+2+3+4+5 = 7 + 8 = 15。

我一開始的做法是，left從1開始累加，當累加(k-1)時，right就從(k+1)開始往上加，直到right>=left為止，若right==left，則找到一對(n, k)。這個方法可以找到正確答案，但實在跑太久，我讓他跑了一個小時，才找到第8對。

想著想著突然間豁然開朗，發現更有效率的方法。新的想法是，已知第一對(n, k)，即是知道一對相等的left, right，從這裡開始。k每加一，left加入(k-1)，因為要納入原本的分隔點(k-1)，而right則減掉k，因為要扣掉新的分隔點k。接著right再從n+1開始累加上去，直到right>=left為止，若right==left，則找到一對(n, k)。然後n, k, left, right的值都保留繼續累加使用。

沒想到這樣的做法竟然快了非常多，馬上答案就出來了！在看到第10對(n, k)的時候簡直太感動了。用這個做法就不用先把答案算出來然後上傳hard code了，Runtime是0.328。

說回這個問題，1 + 2 + 3 + … + (k-1) = (k+1) + (k+2) + … + n，看起來好像是蠻容易滿足的條件，但第10對(n, k)竟然已經是8位數字了！數字真神奇啊。另外，查了資料也發現這個問題可以用數論的Pell’s equation直接求解，但看Wolfram Mathworld和Wikipedia都看不太懂，希望有天可以了解。

 

CODE

#include <iostream>

int main(){

    unsigned long long k, n, count, left, right;

    printf("%10d%10d\n%10d%10d\n", 6, 8, 35, 49);

    for(k=36, n=50, count=0, left=595, right=595; count!=8; ++k){

        left += (k - 1);

        right -= k;

        for(; right<left; ++n)

            right += n;

        if( left == right ){

            printf("%10llu%10llu\n", k, n-1);

            ++count;

        }

    }

    return 0;

}