CFC:复杂市场分析中的质数乘积问题

在解决此问题时，关键在于理解如何通过特定的排列使最终乘积为质数。具体而言，需要找到一个质数与多个1相乘的形式。

最初尝试从1开始向两侧查找质数，但这种方法效率低下且难以实现。因此，调整思路，从已知的质数出发，向两侧寻找1的数量，从而简化了问题的解决方法。

最终答案可以通过计算每个质数位置前后1的数量来确定，公式为：ans += (pre[i] + 1) * (suf[i] + 1) - 1。

以下是具体的代码实现：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
using namespace std;

inline int read() {
    int x = 0;
    char c = getchar();
    while(c <'0' || c > '9') c = getchar();
    while(c >= '0' && c <= '9') x = (x <<3) + (x <<1) + c - '0', c = getchar();
    return x;
}

int T, n, e;
const int N = 2e5 + 10, M = 1e6 + 10;
queue q_0, q_1;
int d[N], pre[N], suf[N];
bool not_prim[M];

void get_prim() {
    not_prim[1] = true;
    for(int i = 2; i         for(int j = 2; i * j             not_prim[i * j] = true;
}

void prepare() {
    for(int i = 1; i <= n; i++) {
        if(i - e > 0 && d[i - e] == 1)
            pre[i] = pre[i - e] + 1;
        else pre[i] = 0;
    }
    for(int i = n; i > 0; i--) {
        if(i + e <= n && d[i + e] == 1)
            suf[i] = suf[i + e] + 1;
        else suf[i] = 0;
    }
}

int main() {
    get_prim();
    T = read();
    while(T--) {
        n = read(), e = read();
        for(int i = 1; i <= n; i++)
            d[i] = read();
        prepare();
        ll ans = 0;
        for(int i = 1; i <= n; i++) {
            if(!not_prim[d[i]]) {
                // printf(" %d %d %d \n", d[i], pre[i], suf[i]);
                ans += 1LL * (pre[i] + 1) * (suf[i] + 1) - 1;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

查看代码