跟出题人题解感觉不是很一样,思维量似乎小一点。
直接说解法:要构造 的答案,就找到一个素数 ,其中 ,于是 区间都可以构造出来, 。这样操作后,问题就剩下构造 的答案。
可行性:要找到符合条件的素数 ,就要求对于任意正整数 , 区间里存在素数。想一下 比较小的情况都符合, 比较大的情况不符合倒是会很奇怪,打表也可以发现题目中的数据范围可以保证可行。
#include<bits/stdc++.h>
using namespace std;
int ans[1000005];
bool isPrime(int x) {
for(int i = 2; i * i <= x; i++) if(x % i == 0) return 0;
return 1;
}
void solve(int n) {
if(n == 0) return;
for(int i = 1; i <= n; i++) {
if(isPrime(n + i)) {
for(int j = i; j <= n; j++)
ans[j] = n + i - j;
solve(i - 1);
return;
}
}
}
int main() {
int n;
cin >> n;
solve(n);
for(int i = 1; i <= n; i++)
printf("%d ", ans[i]);
return 0;
}
全部评论
(2) 回帖