本文最后更新于:2020年4月11日 下午

问题描述

考虑一个可以用数字,括号和运算符(+ // *%)描述的函数$f(n)$。回答$f(n)$,使
$f(1)$至$f(100)$返回不同的质数。

  • 注意,在整数范围内执行除法。

题目分析

使用欧拉的素数生成公式$n ^ 2-n + 41$,我们可以看到在$f(100)$之前有$86$个素数。

首先,如果您不关心长度,只需将剩余的14个值稍微移动一下即可。

例如,如果要管理f(92),则可以通过添加$(n÷92)$$×$$[(92-n$%$92)÷92]×6$等表达式来将$f(92)$增加6。

生产将这种方法减少到294个字节。

有两种方法可以进一步减少这种情况:

  1. 连接多个生成器多项式。

如果存在三个生成多项式 $a(n)·b(n)·c(n)$,则$a(n)+ n / P *(b(n)-a(n))+ n / Q *(c)$

  1. 仅切换Euler表达式的常数部分。

仅切换欧拉方程的最后41个,即$n ^ 2-n + A + n / P * B + n / Q * C +$…

这次,尝试后者。

首先,在后面描述的代码中,当$f(n,X)= n ^ 2-n + X$ 是11个连续质数的列表时,在$X <= 10 ^ 6$的范围内有37个。

核心伪$Code$

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();
	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");
		}
	}
}

本文在 CC BY-NC-ND 4.0( https://creativecommons.org/licenses/by-nc-nd/4.0/deed.zh )协议 的前提下,禁止超过文章30%字数的摘录(对于不超过文章30%字数的摘录,要求在醒目位置注明原文作者与原文链接),同时,在未经作者本人手写签名许可的情况下,禁止任何形式的全文转载,禁止发布任何基于本文的再创作。

题解 AT1314 【マス目と駒】 上一篇
题解 AT3862 【異世界数式】 下一篇
本博客采用 xCss 的 Valine 评论系统,搭配了 Valine-Admin,垃圾评论将会被过滤。所以在评论的时候,请注意您的语言。如果您的评论被过滤但并非垃圾评论,请发邮件到 luosiweimail@gmail.com 进行申诉。