本文共 1732 字，大约阅读时间需要 5 分钟。

为了解决这个问题，我们需要计算Euler公式 ( n^2 + n + 41 ) 在给定区间 ([a, b]) 内生成的质数的百分比。为了高效处理这个问题，我们可以预先计算每个数 ( n ) 是否生成质数，然后在查询时快速统计结果。

方法思路

解决代码

#include 
   
    #include 
    
     #include 
     
      using namespace std;const int maxn = 10000 + 5;int sum[maxn + 1];void init_sum() {    sum[0] = 1;    for (int i = 1; i <= maxn; ++i) {        int x = i * i + i + 41;        if (x <= 1) {            sum[i] = sum[i - 1];            continue;        }        bool is_prime = true;        if (x % 2 == 0 || x % 3 == 0) {            is_prime = false;        } else {            for (int j = 5; j * j <= x; j += 6) {                if (x % j == 0 || x % (j + 2) == 0) {                    is_prime = false;                    break;                }            }        }        sum[i] = is_prime ? sum[i - 1] + 1 : sum[i - 1];    }}int main() {    init_sum();    while (true) {        long long a, b;        if (scanf("%lld%lld", &a, &b) != 2) {            break;        }        if (a > b) {            a = b;        }        long long count = sum[b];        if (a > 0) {            count -= sum[a - 1];        }        long long total = b - a + 1;        double percent = (count * 100.0) / total;        percent = round(percent * 100.0) / 100.0;        printf("%.2f\n", percent);    }    return 0;}
     
    
   

代码解释

这种方法通过预处理阶段将时间复杂度降低到常数时间，确保了在处理大量查询时的高效性。