63byteまで縮めたが、それ以上落とせない…。
http://birthday0410.contest.atcoder.jp/tasks/birthday0410_f
問題
数字と括弧と演算子(+-/*%)で記述可能な関数f(n)を考える。
f(1)～f(100)が異なる素数を返すようなf(n)を答えよ。
なお、除算は整数の範囲で行われる。
解法
オイラーの素数生成式n^2-n+41を使うと、f(100)までの間に86個素数があることがわかる。
まず、長さを気にしないなら残りの14個の値を少しずらしてやればよい。
例えばf(92)をどうにかしたければ +(n/92)*((92-n%92)/92)*6 のような式を加えてやればf(92)だけ6増やしたりできる。
本番はこのアプローチで294byteまで減らした。
もっと減らすには、以下の２つのアプローチがあるようだ。
- 複数の生成多項式を連結する。
- ３つの生成多項式a(n)・b(n)・c(n)があったら、a(n) + n/P*(b(n)-a(n)) + n/Q*(c(n)-b(n))のように連結することでP,Qを境に多項式を切り替える。
- オイラーの式の定数部だけ切り替える。
- オイラーの式の最後の41だけ切り替え、n^2 - n + A + n/P*B + n/Q*C + … とする。
今回は後者を実際に試してみる。
まず、後述のコードでf(n,X) = n^2-n+Xのうち素数が11個連続しているものを列挙すると、X<=10^6の範囲に37個ある。
このうち、以下の５個を以下のようにつなげればよい。
各Xに対し、各文字、空白は素数でなく、*とoは素数となるf(n,X)を示す。
このうち*となる部分を連結する。
注意点は"@"の部分で、n=41以降Xを41から8081に切り替えるためn/41*8040を加算しているが、その場合n>=82で8040が２重に加算される。
@の部分は２重に加算されたときに初めて素数となる場所である。
X=247757のときn>=87でも8040が２重に加算されるが、そこは式を作る段階で8040を引いておけば良い。
41 :**************************************** oo oooo oooooo oooooooo oooooooooo oooo o oo o o oooo ooo|
8081 :o ooooo oo ooo oooooo ooooooo oo oo ************* oo oo oooo oo o o ooooooooo o ooo o oo o oo|
247757 : o o oooo ooo o oooo ooo oo ooo oo oo o oo oo oo **********oo oo ooooo ooo o **************|
14741 :o oo oooooo ooo o ooo ooo ooo oo ooo oo oo ooooo o oo o oo oo ooo ******@@@@@ ooo |
15371 : ooooooooo o o o o ooo ooo ooooooo ooo o o o oooo ooo ************ o o o o oo ooo|まとめると以下の式ができる。空白を除いて63byte。
n*n-n+41 +n/41*8040 +n/54*239676 -n/64*232386 -n/76*630 +n/87*224976
以下11個以上素数が連結している箇所を列挙するコード。
X=14741でn>=82において8040を二重加算する処理は入れていません。
int NP; const int prime_max = 10000000; int p[prime_max]; int cc; void cprime() { int i,j; NP=0; for(i=2;i<prime_max;i++) { if(p[i]) continue; for(j=i*2;j<prime_max;j+=i) p[j]=i; } } void solve() { int f,i,j,k,l,x,y; cprime(); /* check for(x=1;x<=100;x++) { int n=x; y=n*n-n+41+n/41*8040+n/54*239676-n/64*232386-n/76*630+n/87*224976; _P((p[y])?"x":"o"); } _P("\n"); */ for(i=1;i<=1000000;i+=2) { int vis[100]; int ma=0,c=0; for(x=1;x<=100;x++) { y=x*x-x+i; vis[x-1]=p[y]; if(vis[x-1]) c=0; else ma=max(ma,++c); } if(ma>=11) { _P("%8d : %d :",i,ma); FOR(x,100) _P((vis[x])?" ":"o"); _P("|\n"); } } }
まとめ
62byte以下に出来ないか頑張ってみたけどうまく行きませんでした。
