Problem2800 Joseph's Problem

Ozyさんの所で取り上げられている問題。

_int64 r,c;
main(n,k)
{
    for(scanf("%d%d",&n,&k);n-=c;r+=k/n*c*~-c/2+k%n*c)
        c=##########;
    printf("%I64d",r);
}

のようにして解きます。
　%1、%2、%3、……、%n　ではなくて、　%n、%(n-1)、……、%3、%2、%1　みたいに計算する方が、判定式が1つ省けてエレガントです。
　
###の部分についてですが、最短を求める場合は、逆ポーランド記法で全パターンの式を自動生成するプログラムを書いてあげて、その中から条件に当てはまるものを中置記法に変換して全て出力してあげて、それらの式を適当に整理してあげれば最短のものが見つかります。
使える値はnとkと1の3種類、使える二項演算子は+と/と%と-の4種類、使える単項演算子は-と~の2種類としました。
　
どうして式を手作業で最短変換だけではダメで、式の生成プログラムを作る必要があったかと言うと、###に入る式というのは、実は最適な値を算出しなくてよいからです。
最適な値をA(n,k)とすると

(A(n,k)-1)/5+1 ≦ ### ≦ A(n,k)

の範囲に収まれば、Acceptすることが分かっています。
つまり最適な計算式A(n,k)は分かっていますが、微妙に式が長くなってしまうので、より簡略化して劣化した式を見つけ出す必要があるわけです。
　
（###の値は、常に1でも正しい答えが出ますが、計算時間がかかりすぎてTLEになるだけです……つまり大きすぎると不正解が出るけど、小さすぎるとTLEになっちゃう…0以下だと無限ループに陥ってしまうので、そうならない、何らかの式を探す必要があるわけです）
　
尚、　A(n,k) = (n-k%n-1)/(k/n+1)+1　です。