莱芜市住房和城乡建设厅网站北京代理注册记账公司

莱芜市住房和城乡建设厅网站,北京代理注册记账公司,摄影作品网站风景,只用php做网站题目描述 一位科学家正在尝试制造一种非常大的晶体#xff0c;具体来说是一种大的碳晶体。他认为#xff0c;既然钻石是碳的晶体并且非常珍贵#xff0c;那么从长远来看#xff0c;他的新碳晶体也会像钻石一样珍贵。他晶体中的原子无法自然结合在一起#xff0c;因此他希望…题目描述一位科学家正在尝试制造一种非常大的晶体具体来说是一种大的碳晶体。他认为既然钻石是碳的晶体并且非常珍贵那么从长远来看他的新碳晶体也会像钻石一样珍贵。他晶体中的原子无法自然结合在一起因此他希望在晶体中心施加一个强大的力吸引所有碳原子并使它们保持在一起。钻石晶体中的碳原子可以看作是放置在一个立方体中。科学家也希望将他的晶体碳原子放置在一个N×N×NN \times N \times NN×N×N的立方体中其中NNN为偶数。如果该立方体的中心是(0,0,0)(0, 0, 0)(0,0,0)且所有边均平行于xyxyxy、yzyzyz或xzxzxz平面则所有原子都将放置在三维整数坐标上。因此如果(x,y,z)(x, y, z)(x,y,z)是N×N×NN \times N \times NN×N×N立方体中某个原子的坐标则xxx、yyy和zzz为整数且满足(−N/2≤x,y,z≤N/2)(-N/2 \le x, y, z \le N/2)(−N/2≤x,y,z≤N/2)。由于中心的强大引力会吸引所有原子因此原子的放置方式需确保没有任何原子位于中心和另一个原子之间。例如如果坐标(2,2,2)(2, 2, 2)(2,2,2)处有一个原子则不应在坐标(1,1,1)(1, 1, 1)(1,1,1)处放置原子因为(1,1,1)(1, 1, 1)(1,1,1)处的原子会阻挡(2,2,2)(2, 2, 2)(2,2,2)与中心之间的引力。同样地如果(1,1,1)(1, 1, 1)(1,1,1)处有原子则(2,2,2)(2, 2, 2)(2,2,2)处不应有原子。给定要制造晶体的立方体尺寸边长你的任务是找出在上述约束下可以放置的最大原子数。输入格式输入文件最多包含303030行。每行包含一个偶数整数NNN0N≤2000000 N \le 2000000N≤200000表示科学家计划放置原子的立方体的边长。输入以一行NNN的值为000结束。输出格式对于除最后一行外的每一行输入输出一行。该行应包含输出序号格式为Crystal i:和一个整数表示可以放置的最大原子数。样例输入4 2 0样例输出Crystal 1: 98 Crystal 2: 26数学基础莫比乌斯函数与莫比乌斯反演一、莫比乌斯函数莫比乌斯函数μ(n)\mu(n)μ(n)是定义在正整数上的函数μ(n){1如果 n1(−1)k如果 n 是 k 个不同质数的乘积0如果 n 被一个质数的平方整除 \mu(n) \begin{cases} 1 \text{如果 } n 1 \\ (-1)^k \text{如果 } n \text{ 是 } k \text{ 个不同质数的乘积} \\ 0 \text{如果 } n \text{ 被一个质数的平方整除} \end{cases}μ(n)⎩⎨⎧​1(−1)k0​如果n1如果n是k个不同质数的乘积如果n被一个质数的平方整除​重要性质积性函数如果gcd⁡(a,b)1\gcd(a, b) 1gcd(a,b)1则μ(ab)μ(a)μ(b)\mu(ab) \mu(a)\mu(b)μ(ab)μ(a)μ(b)求和性质∑d∣nμ(d){1如果 n10如果 n1 \sum_{d \mid n} \mu(d) \begin{cases} 1 \text{如果 } n 1 \\ 0 \text{如果 } n 1 \end{cases}d∣n∑​μ(d){10​如果n1如果n1​二、莫比乌斯反演设f(n)f(n)f(n)和g(n)g(n)g(n)是定义在正整数上的两个函数。第一形式约数和形式如果f(n)∑d∣ng(d)f(n) \sum_{d \mid n} g(d)f(n)∑d∣n​g(d)那么g(n)∑d∣nμ(d)f(nd)g(n) \sum_{d \mid n} \mu(d) f\left(\frac{n}{d}\right)g(n)∑d∣n​μ(d)f(dn​)第二形式倍数和形式如果f(n)∑n∣dg(d)f(n) \sum_{n \mid d} g(d)f(n)∑n∣d​g(d)那么g(n)∑n∣dμ(dn)f(d)g(n) \sum_{n \mid d} \mu\left(\frac{d}{n}\right) f(d)g(n)∑n∣d​μ(nd​)f(d)莫比乌斯反演可以看作是容斥原理的数论形式。当我们知道一个包含所有因子的函数f(n)f(n)f(n)时可以用莫比乌斯函数筛出我们真正关心的函数g(n)g(n)g(n)。题目分析与解题思路1. 问题转化题目要求在一个边长为偶数NNN的立方体网格中放置尽可能多的点原子使得从原点(0,0,0)(0,0,0)(0,0,0)即立方体中心到任意一个被放置的点的线段上没有其他被放置的点整数点存在。换句话说所有被放置的点必须是从原点可见的即从原点到该点的线段上不存在其他整数点除了端点。在三维整数网格中一个点(x,y,z)(x, y, z)(x,y,z)从原点可见的充要条件是gcd⁡(∣x∣,∣y∣,∣z∣)1 \gcd(|x|, |y|, |z|) 1gcd(∣x∣,∣y∣,∣z∣)1理由如果gcd⁡(∣x∣,∣y∣,∣z∣)d1\gcd(|x|,|y|,|z|) d 1gcd(∣x∣,∣y∣,∣z∣)d1那么点(xd,yd,zd)(\frac{x}{d}, \frac{y}{d}, \frac{z}{d})(dx​,dy​,dz​)也在该线段上并且更靠近原点从而原点与该点之间存在其他整数点违反了规则。因此我们的目标是在坐标范围[−M,M][-M, M][−M,M]内其中MN/2M N/2MN/2统计所有满足gcd⁡(∣x∣,∣y∣,∣z∣)1\gcd(|x|,|y|,|z|) 1gcd(∣x∣,∣y∣,∣z∣)1的整数点(x,y,z)(x, y, z)(x,y,z)的数量。注意原点(0,0,0)(0,0,0)(0,0,0)的gcd⁡\gcdgcd定义为000我们需要排除原点。2. 数学建模与推导设MN/2M N/2MN/2坐标范围[−M,M][-M, M][−M,M]。我们定义g(d)g(d)g(d) 满足gcd⁡(∣x∣,∣y∣,∣z∣)d\gcd(|x|,|y|,|z|) dgcd(∣x∣,∣y∣,∣z∣)d的点数d≥1d \ge 1d≥1f(d)f(d)f(d) 满足d∣gcd⁡(∣x∣,∣y∣,∣z∣)d \mid \gcd(|x|,|y|,|z|)d∣gcd(∣x∣,∣y∣,∣z∣)的点数即三个坐标都是ddd的倍数显然有f(d)∑k≥1g(k⋅d) f(d) \sum_{k \ge 1} g(k \cdot d)f(d)k≥1∑​g(k⋅d)这是因为如果gcd⁡\gcdgcd是ddd的倍数那么它可以是d,2d,3d,…d, 2d, 3d, \dotsd,2d,3d,…。使用第二形式的莫比乌斯反演令n1n 1n1g(1)∑d≥1μ(d)f(d) g(1) \sum_{d \ge 1} \mu(d) f(d)g(1)d≥1∑​μ(d)f(d)这里g(1)g(1)g(1)就是我们需要的可见点数gcd⁡1\gcd 1gcd1。3. 计算f(d)f(d)f(d)对于给定的dddf(d)f(d)f(d)是三个坐标都是ddd的倍数的点数。在范围[−M,M][-M, M][−M,M]中xxx是ddd的倍数的值有000±d,±2d,…,±kd\pm d, \pm 2d, \dots, \pm kd±d,±2d,…,±kd其中k⌊M/d⌋k \lfloor M/d \rfloork⌊M/d⌋所以每个坐标有2k12k 12k1个可能值。三个坐标独立总共有(2k1)3(2k 1)^3(2k1)3种组合。但原点(0,0,0)(0,0,0)(0,0,0)的gcd⁡\gcdgcd是000不属于gcd⁡d≥1\gcd d \ge 1gcdd≥1的情况所以排除原点f(d)(2⋅⌊M/d⌋1)3−1 f(d) (2 \cdot \lfloor M/d \rfloor 1)^3 - 1f(d)(2⋅⌊M/d⌋1)3−14. 最终公式将f(d)f(d)f(d)代入反演公式得到可见点数∑d1Mμ(d)⋅[(2⋅⌊M/d⌋1)3−1] \text{可见点数} \sum_{d1}^{M} \mu(d) \cdot \left[ (2 \cdot \lfloor M/d \rfloor 1)^3 - 1 \right]可见点数d1∑M​μ(d)⋅[(2⋅⌊M/d⌋1)3−1]其中MN/2M N/2MN/2。5. 验证样例对于N4N 4N4M2M 2M2d1d 1d1μ(1)1\mu(1) 1μ(1)1⌊2/1⌋2\lfloor 2/1 \rfloor 2⌊2/1⌋2(2⋅21)3−153−1124(2 \cdot 2 1)^3 - 1 5^3 - 1 124(2⋅21)3−153−1124d2d 2d2μ(2)−1\mu(2) -1μ(2)−1⌊2/2⌋1\lfloor 2/2 \rfloor 1⌊2/2⌋1(2⋅11)3−133−126(2 \cdot 1 1)^3 - 1 3^3 - 1 26(2⋅11)3−133−126d3d 3d3μ(3)−1\mu(3) -1μ(3)−1⌊2/3⌋0\lfloor 2/3 \rfloor 0⌊2/3⌋0(2⋅01)3−10(2 \cdot 0 1)^3 - 1 0(2⋅01)3−10d4d 4d4μ(4)0\mu(4) 0μ(4)0⌊2/4⌋0\lfloor 2/4 \rfloor 0⌊2/4⌋0(2⋅01)3−10(2 \cdot 0 1)^3 - 1 0(2⋅01)3−10总和124−2698124 - 26 98124−2698与样例输出一致。对于N2N 2N2M1M 1M1d1d 1d1μ(1)1\mu(1) 1μ(1)1⌊1/1⌋1\lfloor 1/1 \rfloor 1⌊1/1⌋1(2⋅11)3−133−126(2 \cdot 1 1)^3 - 1 3^3 - 1 26(2⋅11)3−133−126d2d 2d2μ(2)−1\mu(2) -1μ(2)−1⌊1/2⌋0\lfloor 1/2 \rfloor 0⌊1/2⌋0(2⋅01)3−10(2 \cdot 0 1)^3 - 1 0(2⋅01)3−10总和262626与样例输出一致。算法设计与实现1. 算法步骤预处理莫比乌斯函数使用线性筛法计算μ(1)\mu(1)μ(1)到μ(Mmax⁡)\mu(M_{\max})μ(Mmax​)其中Mmax⁡100000M_{\max} 100000Mmax​100000因为N≤200000N \le 200000N≤200000所以M≤100000M \le 100000M≤100000。处理每个查询读入NNN偶数计算MN/2M N/2MN/2。初始化答案ans0ans 0ans0。对ddd从111到MMM循环累加μ(d)⋅[(2⋅⌊M/d⌋1)3−1]\mu(d) \cdot \left[ (2 \cdot \lfloor M/d \rfloor 1)^3 - 1 \right]μ(d)⋅[(2⋅⌊M/d⌋1)3−1]。输出Crystal i: ans。2. 时间复杂度分析预处理莫比乌斯函数O(Mmax⁡)O(M_{\max})O(Mmax​)其中Mmax⁡100000M_{\max} 100000Mmax​100000。每个查询O(M)O(M)O(M)其中M≤100000M \le 100000M≤100000。总操作数最多303030个查询约3×1063 \times 10^63×106次运算在合理范围内。3. 空间复杂度分析需要存储莫比乌斯函数数组大小为O(Mmax⁡)O(M_{\max})O(Mmax​)即100001100001100001个整数空间充足。代码实现// Make a Crystal// UVa ID: 11014// Verdict: Accepted// Submission Date: 2025-12-17// UVa Run Time: 0.000s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;typedeflonglongLL;constintMAXM100000;intmu[MAXM5];boolisPrime[MAXM5];vectorintprimes;// 预处理莫比乌斯函数使用线性筛法voidsieve(){fill(isPrime,isPrimeMAXM1,true);mu[1]1;for(inti2;iMAXM;i){if(isPrime[i]){primes.push_back(i);mu[i]-1;// 质数的莫比乌斯函数值为 -1}for(intp:primes){if(i*pMAXM)break;isPrime[i*p]false;if(i%p0){mu[i*p]0;// 有平方因子break;}else{mu[i*p]-mu[i];// 积性函数性质}}}}intmain(){sieve();intcaseNo1;intN;while(scanf(%d,N)1N!0){LL MN/2;LL ans0;for(LL d1;dM;d){LL tM/d;// floor(M/d)LL term(2*t1);termterm*term*term-1;// (2t1)^3 - 1ansmu[d]*term;}printf(Crystal %d: %lld\n,caseNo,ans);}return0;}代码说明线性筛法计算莫比乌斯函数初始化所有数为质数μ(1)1\mu(1) 1μ(1)1。遍历iii从222到MAXMMAXMMAXM如果iii是质数加入质数表μ(i)−1\mu(i) -1μ(i)−1。用当前质数表筛去合数i×pi \times pi×p如果iii能被ppp整除则i×pi \times pi×p有平方因子μ(i×p)0\mu(i \times p) 0μ(i×p)0。否则μ(i×p)−μ(i)\mu(i \times p) -\mu(i)μ(i×p)−μ(i)积性函数性质。主循环读取每个NNN直到N0N 0N0结束。计算MN/2M N/2MN/2。对ddd从111到MMM累加贡献。输出结果注意使用%lld格式输出long long类型。注意事项使用long long类型存储中间结果和答案避免溢出。ddd循环上界为MMM因为当dMd MdM时⌊M/d⌋0\lfloor M/d \rfloor 0⌊M/d⌋0贡献为000。算法优化思考虽然当前算法已经可以通过题目测试但还可以进一步优化整除分块优化计算∑d1Mμ(d)⋅[(2⋅⌊M/d⌋1)3−1]\sum_{d1}^{M} \mu(d) \cdot \left[ (2 \cdot \lfloor M/d \rfloor 1)^3 - 1 \right]∑d1M​μ(d)⋅[(2⋅⌊M/d⌋1)3−1]时⌊M/d⌋\lfloor M/d \rfloor⌊M/d⌋的值在连续区间内相同可以使用整除分块将复杂度从O(M)O(M)O(M)降为O(M)O(\sqrt{M})O(M​)。预处理前缀和可以预处理莫比乌斯函数的前缀和结合整除分块进一步优化。记忆化对于重复的MMM值可以缓存计算结果。但对于本题M≤100000M \le 100000M≤100000且最多303030个查询的情况当前O(M)O(M)O(M)算法已经足够高效。总结本题的核心在于将几何约束转化为数论条件从原点可见的点等价于gcd⁡(∣x∣,∣y∣,∣z∣)1\gcd(|x|,|y|,|z|) 1gcd(∣x∣,∣y∣,∣z∣)1。通过引入莫比乌斯函数和莫比乌斯反演我们避免了复杂的容斥计数得到了简洁高效的数学公式。算法实现主要分为两部分预处理莫比乌斯函数线性筛法对每个查询计算和式掌握莫比乌斯反演这一工具对于解决类似的数论计数问题非常有帮助它能够将复杂的容斥过程转化为简洁的数学表达式是算法竞赛中处理gcd⁡\gcdgcd相关计数问题的利器。