题目问题分析我们需要计算朋友进入餐厅时最大叫服务员次数与最小叫服务员次数的差值分布值。关键观察 最大次数按顺序1、2、…、N进入时每个质数或质数幂次的朋友都会触发服务员呼叫总次数等于质数幂次数量1包含数字1的首次呼叫。 最小次数按最优顺序进入时仅质数会触发服务员呼叫总次数等于质数数量1。 分布值 最大次数 - 最小次数 质数幂次数量1-质数数量1 质数高次幂质数的平方及以上的数量 1修正项。核心结论分布值的计算公式为 当N1时分布值为0。 当N≥2时分布值 所有质数p≤√N的高次幂数量之和 1。 其中质数p的高次幂数量为floor(log_p N) - 1即p²、p³…≤N的个数。算法步骤:预处理质数使用埃拉托斯特尼筛法生成所有≤1e6的质数因为N最大为1e12√N1e6。计算高次幂数量 对每个质数p≤√N计算最大的k使得pᵏ≤N贡献k-1到总和高次幂数量。计算分布值总和加1即为最终结果。代码实现#include iostream #include vector #include cmath using namespace std; const int MAX_SQRT 1e6; vectorint primes; void sieve() { vectorbool isprime(MAXSQRT 1, true); isprime[0] isprime[1] false; for (int i 2; i * i MAX_SQRT; i) { if (is_prime[i]) { for (int j i * i; j MAX_SQRT; j i) { is_prime[j] false; } } } for (int i 2; i MAX_SQRT; i) { if (isprime[i]) primes.pushback(i); } } long long compute_distribution(long long N) { if (N 1) return 0; long long sqrt_N sqrt(N); while ((sqrtN 1) * (sqrtN 1) N) sqrt_N; while (sqrtN * sqrtN N) sqrt_N--; long long sum 0; double ln_N log(N); for (int p : primes) { if (p sqrt_N) break; int k (int)(ln_N / log(p)); // 验证k的准确性 int128 current 1; int actual_k 0; while (current N / p) { current * p; actual_k; } if (actualk 2) sum actualk - 1; } return sum 1; } int main() { ios::syncwithstdio(false); cin.tie(nullptr); sieve(); int T; cin T; for (int casenum 1; casenum T; case_num) { long long N; cin N; cout Case # casenum : computedistribution(N) \n; } return 0; } //----------------------------防伪标-----------------------复杂度分析:预处理筛法时间复杂度O(n log log n)n1e6约0.1秒。查询处理每个测试用例遍历约78498个质数每个质数的高次幂计算时间O(log_p N)总时间复杂度O(T π(√N) log N)对于T1e3完全满足6秒时间限制。关键优化:使用int128避免大数乘法溢出问题。 通过浮点数快速估算指数k再用整数乘法验证准确性平衡效率与精度。
P13376题解
题目问题分析我们需要计算朋友进入餐厅时最大叫服务员次数与最小叫服务员次数的差值分布值。关键观察 最大次数按顺序1、2、…、N进入时每个质数或质数幂次的朋友都会触发服务员呼叫总次数等于质数幂次数量1包含数字1的首次呼叫。 最小次数按最优顺序进入时仅质数会触发服务员呼叫总次数等于质数数量1。 分布值 最大次数 - 最小次数 质数幂次数量1-质数数量1 质数高次幂质数的平方及以上的数量 1修正项。核心结论分布值的计算公式为 当N1时分布值为0。 当N≥2时分布值 所有质数p≤√N的高次幂数量之和 1。 其中质数p的高次幂数量为floor(log_p N) - 1即p²、p³…≤N的个数。算法步骤:预处理质数使用埃拉托斯特尼筛法生成所有≤1e6的质数因为N最大为1e12√N1e6。计算高次幂数量 对每个质数p≤√N计算最大的k使得pᵏ≤N贡献k-1到总和高次幂数量。计算分布值总和加1即为最终结果。代码实现#include iostream #include vector #include cmath using namespace std; const int MAX_SQRT 1e6; vectorint primes; void sieve() { vectorbool isprime(MAXSQRT 1, true); isprime[0] isprime[1] false; for (int i 2; i * i MAX_SQRT; i) { if (is_prime[i]) { for (int j i * i; j MAX_SQRT; j i) { is_prime[j] false; } } } for (int i 2; i MAX_SQRT; i) { if (isprime[i]) primes.pushback(i); } } long long compute_distribution(long long N) { if (N 1) return 0; long long sqrt_N sqrt(N); while ((sqrtN 1) * (sqrtN 1) N) sqrt_N; while (sqrtN * sqrtN N) sqrt_N--; long long sum 0; double ln_N log(N); for (int p : primes) { if (p sqrt_N) break; int k (int)(ln_N / log(p)); // 验证k的准确性 int128 current 1; int actual_k 0; while (current N / p) { current * p; actual_k; } if (actualk 2) sum actualk - 1; } return sum 1; } int main() { ios::syncwithstdio(false); cin.tie(nullptr); sieve(); int T; cin T; for (int casenum 1; casenum T; case_num) { long long N; cin N; cout Case # casenum : computedistribution(N) \n; } return 0; } //----------------------------防伪标-----------------------复杂度分析:预处理筛法时间复杂度O(n log log n)n1e6约0.1秒。查询处理每个测试用例遍历约78498个质数每个质数的高次幂计算时间O(log_p N)总时间复杂度O(T π(√N) log N)对于T1e3完全满足6秒时间限制。关键优化:使用int128避免大数乘法溢出问题。 通过浮点数快速估算指数k再用整数乘法验证准确性平衡效率与精度。
