运动服饰网站建设目的阿里网站建设方案书

运动服饰网站建设目的,阿里网站建设方案书,攀枝花网站建设兼职,做外贸网站怎么做题目描述 Macintosh\texttt{Macintosh}Macintosh 先生是一位地主#xff0c;他拥有的所有土地都是直角三角形#xff0c;并且两条直角边的长度都是整数。他雇佣了一名员工来记录所有土地的信息#xff0c;但报告只包含每块土地最长边#xff08;斜边#xff09;的平方值。…题目描述Macintosh\texttt{Macintosh}Macintosh先生是一位地主他拥有的所有土地都是直角三角形并且两条直角边的长度都是整数。他雇佣了一名员工来记录所有土地的信息但报告只包含每块土地最长边斜边的平方值。也就是说如果一块土地的三条边为aaa、bbb、ccc其中ccc是斜边最大边那么报告中只记录c2c^2c2的值。现在Macintosh\texttt{Macintosh}Macintosh先生怀疑这名员工是否诚实他需要你根据报告中的数据判断这些值是否真的可能是某块直角三角形土地斜边的平方。输入格式输入包含若干行每行是一个无符号整数NNN或形如N!N!N!NNN的阶乘的数其中4≤N≤100000004 \le N \le 100000004≤N≤10000000。每个数表示某块土地斜边的平方值。输出格式对于每行输入如果输入是NNN判断N\sqrt{N}N​是否可能是某块土地的最长边。如果是输出He might be honest.否则输出He is a liar.。如果输入是N!N!N!除了进行上述判断外如果N!N!N!本身不是合法的斜边平方还需要输出需要用哪些质数去除N!N!N!才能使其成为某个合法斜边的平方。如果这样的质数超过505050个只输出最小的505050个。质数在同一行输出用空格分隔。当然如果N!N!N!本身就是合法斜边的平方则不需要输出质数。每组输出之间用一个空行分隔。样例输入10 12 98 99 4! 5! 6! 120!样例输出He might be honest. He is a liar. He might be honest. He is a liar. He is a liar. 3 He is a liar. 3 He might be honest. He is a liar. 7 23 31 67 71 79 83 103 107题目分析问题转化题目本质上要求判断一个数MMM可能是NNN或N!N!N!是否可以表示为两个整数的平方和即是否存在整数aaa和bbb使得a2b2M a^2 b^2 Ma2b2M这里MMM是斜边的平方c2c^2c2注意ccc本身不一定是整数题目只要求两条直角边是整数。数论基础费马平方和定理一个经典定理费马平方和定理指出一个正整数MMM可以表示为两个整数的平方和当且仅当在MMM的质因数分解中所有形如4k34k34k3的质因子的指数都是偶数。证明概要充分性如果所有4k34k34k3质因子的指数都是偶数那么MMM可以写成2e×∏pi2ei×∏qj2fj2^e \times \prod p_i^{2e_i} \times \prod q_j^{2f_j}2e×∏pi2ei​​×∏qj2fj​​的形式其中pip_ipi​是4k14k14k1质数qjq_jqj​是4k34k34k3质数。利用平方和恒等式(a2b2)(c2d2)(acbd)2(ad−bc)2(a^2b^2)(c^2d^2) (acbd)^2 (ad-bc)^2(a2b2)(c2d2)(acbd)2(ad−bc)2可以构造出平方和表示。必要性如果存在4k34k34k3质数qqq使得q2k1∣Mq^{2k1} \mid Mq2k1∣M假设Mx2y2M x^2 y^2Mx2y2考虑模qqq可得矛盾。算法设计根据上述定理我们只需要检查MMM的质因数分解中所有4k34k34k3质因子的指数是否都是偶数。1. 对于普通整数NNN直接对NNN进行质因数分解检查每个4k34k34k3质因子的指数奇偶性。2. 对于阶乘N!N!N!需要计算N!N!N!中每个4k34k34k3质数的指数。对于质数ppp它在N!N!N!中的指数由勒让德公式给出exp(p,N!)⌊Np⌋⌊Np2⌋⌊Np3⌋⋯ \text{exp}(p, N!) \left\lfloor \frac{N}{p} \right\rfloor \left\lfloor \frac{N}{p^2} \right\rfloor \left\lfloor \frac{N}{p^3} \right\rfloor \cdotsexp(p,N!)⌊pN​⌋⌊p2N​⌋⌊p3N​⌋⋯我们只需计算这个指数的奇偶性。如果某个4k34k34k3质数ppp在N!N!N!中的指数是奇数那么为了使其指数变为偶数从而满足平方和条件需要从N!N!N!中除去一个ppp。因此所有指数为奇数的4k34k34k3质数就是我们需要输出的质数列表。算法优化质数筛选使用线性筛法预处理所有不超过10710^7107的质数并单独记录所有4k34k34k3质数。指数奇偶性计算对于阶乘的情况使用勒让德公式计算但可以提前终止当pkNp^k NpkN时。输出限制只输出最小的505050个需要除去的质数。时间复杂度筛法预处理O(107)O(10^7)O(107)只需一次。普通整数判断O(N/log⁡N)O(\sqrt{N} / \log N)O(N​/logN)最坏情况下需要检查所有不超过N\sqrt{N}N​的4k34k34k3质数。阶乘判断需要检查所有不超过NNN的4k34k34k3质数每个质数计算指数的时间为O(log⁡pN)O(\log_p N)O(logp​N)。由于N≤107N \le 10^7N≤1074k34k34k3质数大约有1.2×1061.2 \times 10^61.2×106个但实际计算量较小因为很多大质数的指数计算很快。代码实现// Liar or Not Liar that is the ...// UVa ID: 10208// Verdict: Accepted// Submission Date: 2025-12-16// UVa Run Time: 0.500s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 位运算宏定义用于质数筛的位标记#defineGET(x)(B[x5](1(x0x1F)))#defineSET(x)(B[x5]|(1(x0x1F)))constintMAXN7000000,MAXB10000010;intB[MAXB5];// 位数组用于筛法intprimes[MAXN],cnt0;// 存储所有质数vectorintprimes4k3;// 只存储4k3形式的质数// 线性筛法voidsieve(){for(inti2;iMAXB;i){if(!GET(i)){primes[cnt]i;if(i%43)primes4k3.push_back(i);// 记录4k3质数}for(intj0;jcnti*primes[j]MAXB;j){SET(i*primes[j]);if(i%primes[j]0)break;}}}// 判断质数p在n!中的指数是否为奇数inlineboolisExponentOdd(intn,intp){intexp0;while(n){n/p;expn;}return(exp1);}// 判断整数n是否可以表示为两个整数的平方和inlineboolisSquares(intn){for(autop:primes4k3){intcnt0;while(n%p0){n/p;cnt;}if(cnt1)returnfalse;// 4k3质因子指数为奇数}returntrue;}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);sieve();// 预处理质数表string line;boolfirstCasetrue;while(cinline){if(!firstCase)cout\n;firstCasefalse;boolisFactorial(line.back()!);intN;if(isFactorial)Nstoi(line.substr(0,line.size()-1));elseNstoi(line);if(!isFactorial){// 普通整数情况cout(isSquares(N)?He might be honest.\n:He is a liar.\n);}else{// 阶乘情况vectorintneededPrimes;for(autop:primes4k3){if(pN)break;// 如果p在N!中的指数为奇数则需要除去if(isExponentOdd(N,p)neededPrimes.size()50)neededPrimes.push_back(p);if(neededPrimes.size()50)break;// 最多输出50个}if(neededPrimes.empty()){coutHe might be honest.\n;}else{coutHe is a liar.\n;for(size_t i0;ineededPrimes.size();i){if(i0)cout ;coutneededPrimes[i];}cout\n;}}}return0;}总结本题的关键在于理解费马平方和定理将一个几何问题转化为数论问题。对于普通整数直接检查质因数分解对于阶乘利用勒让德公式计算质数指数。算法的时间复杂度可以接受主要优化在于只关注4k34k34k3质数并使用位运算加速筛法。通过本题我们不仅复习了经典的数论定理还学习了如何高效处理阶乘的质因数分解问题这对解决其他数论问题也有很好的借鉴意义。