読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

お誕生日コンテスト: F - おいらの素数生成式

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まで減らした。

もっと減らすには、以下の2つのアプローチがあるようだ。

  1. 複数の生成多項式を連結する。
    • 3つの生成多項式a(n)・b(n)・c(n)があったら、a(n) + n/P*(b(n)-a(n)) + n/Q*(c(n)-b(n))のように連結することでP,Qを境に多項式を切り替える。
  2. オイラーの式の定数部だけ切り替える。
    • オイラーの式の最後の41だけ切り替え、n^2 - n + A + n/P*B + n/Q*C + … とする。

今回は後者を実際に試してみる。
まず、後述のコードでf(n,X) = n^2-n+Xのうち素数が11個連続しているものを列挙すると、X<=10^6の範囲に37個ある。

このうち、以下の5個を以下のようにつなげればよい。
各Xに対し、各文字、空白は素数でなく、*とoは素数となるf(n,X)を示す。
このうち*となる部分を連結する。
注意点は"@"の部分で、n=41以降Xを41から8081に切り替えるためn/41*8040を加算しているが、その場合n>=82で8040が2重に加算される。
@の部分は2重に加算されたときに初めて素数となる場所である。
X=247757のときn>=87でも8040が2重に加算されるが、そこは式を作る段階で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以下に出来ないか頑張ってみたけどうまく行きませんでした。

広告を非表示にする