Captain Flint and Crew Recruitment

Captain Flint and Crew Recruitment

思路

题目大意: 如果一个整数 $x$可以被表示成两个质数 $p$ 和 $q(p\ne q)$的积,那我们可以把他叫做为近质数.

输入一个整数$n$,请将它表示成四个不同的正整数的和,要求其中三个是近质数

我们先列出最小的近质数并寻早规律.

可以看到,最小的三个近质数分别为 $2\ast 3,2\ast 5,2\ast 7（6,10,14)$

那也就是说,小于$(6+10+14+1=31)$ 的 $n$ 无法被如此表示.

接下来我们考虑重复的情况. 当$n$大于$(6+10+14+14=44)$的时候,无需考虑重复问题.

那就只需要看看三个特例$(6,10,14重复)$能不能被其他的方案排列.

$3\ast 515$也是近质数,因此我们很容易得到

$610146$ 的替代: $610155$

$6101410$ 的替代:$610159$

$6101414$ 的替代: $6101513$

对这三个特例做一个特判即可 时间复杂度为$O(1)$

#include<bits/stdc++.h>using namespace std; int main() {int _;scanf("%d", &_);while (_--) {int n;scanf("%d", &n);// 6 10 14if (n <= 30) {puts("NO");continue;}puts("YES");if (n == 36) {printf("6 10 15 5\n");continue;}if (n == 40) {printf("6 10 15 9\n");continue;}if (n == 44) {printf("6 10 15 13\n");continue;}printf("6 10 14 %d\n", n - 30);} }

总结

以上是生活随笔为你收集整理的Captain Flint and Crew Recruitment的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。