UVa 10208 Liar or Not Liar that is the ...

题目描述

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使得：

a2+b2=M a^2 + b^2 = Ma2+b2=M

这里MMM是斜边的平方c2c^2c2，注意ccc本身不一定是整数（题目只要求两条直角边是整数）。

数论基础：费马平方和定理

一个经典定理（费马平方和定理）指出：

一个正整数MMM可以表示为两个整数的平方和，当且仅当在MMM的质因数分解中，所有形如4k+34k+34k+3的质因子的指数都是偶数。

证明概要：

• 充分性：如果所有4k+34k+34k+3质因子的指数都是偶数，那么MMM可以写成2e×∏pi2ei×∏qj2fj2^e \times \prod p_i^{2e_i} \times \prod q_j^{2f_j}2e×∏pi2ei​​×∏qj2fj​​的形式，其中pip_ipi​是4k+14k+14k+1质数，qjq_jqj​是4k+34k+34k+3质数。利用平方和恒等式(a2+b2)(c2+d2)=(ac+bd)2+(ad−bc)2(a^2+b^2)(c^2+d^2) = (ac+bd)^2 + (ad-bc)^2(a2+b2)(c2+d2)=(ac+bd)2+(ad−bc)2，可以构造出平方和表示。
• 必要性：如果存在4k+34k+34k+3质数qqq使得q2k+1∣Mq^{2k+1} \mid Mq2k+1∣M，假设M=x2+y2M = x^2 + y^2M=x2+y2，考虑模qqq可得矛盾。

算法设计

根据上述定理，我们只需要检查MMM的质因数分解中所有4k+34k+34k+3质因子的指数是否都是偶数。

1. 对于普通整数NNN

直接对NNN进行质因数分解，检查每个4k+34k+34k+3质因子的指数奇偶性。

2. 对于阶乘N!N!N!

需要计算N!N!N!中每个4k+34k+34k+3质数的指数。对于质数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​⌋+⋯

我们只需计算这个指数的奇偶性。如果某个4k+34k+34k+3质数ppp在N!N!N!中的指数是奇数，那么为了使其指数变为偶数（从而满足平方和条件），需要从N!N!N!中除去一个ppp。因此，所有指数为奇数的4k+34k+34k+3质数就是我们需要输出的质数列表。

算法优化

1. 质数筛选：使用线性筛法预处理所有不超过10710^7107的质数，并单独记录所有4k+34k+34k+3质数。
2. 指数奇偶性计算：对于阶乘的情况，使用勒让德公式计算，但可以提前终止（当pk>Np^k > Npk>N时）。
3. 输出限制：只输出最小的505050个需要除去的质数。

时间复杂度

• 筛法预处理：O(107)O(10^7)O(107)，只需一次。
• 普通整数判断：O(N/log⁡N)O(\sqrt{N} / \log N)O(N​/logN)，最坏情况下需要检查所有不超过N\sqrt{N}N​的4k+34k+34k+3质数。
• 阶乘判断：需要检查所有不超过NNN的4k+34k+34k+3质数，每个质数计算指数的时间为O(log⁡pN)O(\log_p N)O(logp​N)。由于N≤107N \le 10^7N≤107，4k+34k+34k+3质数大约有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//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 位运算宏定义，用于质数筛的位标记#defineGET(x)(B[x>>5]&(1<<(x&0x1F)))#defineSET(x)(B[x>>5]|=(1<<(x&0x1F)))constintMAXN=7000000,MAXB=10000010;intB[MAXB>>5];// 位数组，用于筛法intprimes[MAXN],cnt=0;// 存储所有质数vector<int>primes4k3;// 只存储4k+3形式的质数// 线性筛法voidsieve(){for(inti=2;i<MAXB;i++){if(!GET(i)){primes[cnt++]=i;if(i%4==3)primes4k3.push_back(i);// 记录4k+3质数}for(intj=0;j<cnt&&i*primes[j]<MAXB;j++){SET(i*primes[j]);if(i%primes[j]==0)break;}}}// 判断质数p在n!中的指数是否为奇数inlineboolisExponentOdd(intn,intp){intexp=0;while(n){n/=p;exp+=n;}return(exp&1);}// 判断整数n是否可以表示为两个整数的平方和inlineboolisSquares(intn){for(autop:primes4k3){intcnt=0;while(n%p==0){n/=p;cnt++;}if(cnt&1)returnfalse;// 4k+3质因子指数为奇数}returntrue;}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);sieve();// 预处理质数表string line;boolfirstCase=true;while(cin>>line){if(!firstCase)cout<<'\n';firstCase=false;boolisFactorial=(line.back()=='!');intN;if(isFactorial)N=stoi(line.substr(0,line.size()-1));elseN=stoi(line);if(!isFactorial){// 普通整数情况cout<<(isSquares(N)?"He might be honest.\n":"He is a liar.\n");}else{// 阶乘情况vector<int>neededPrimes;for(autop:primes4k3){if(p>N)break;// 如果p在N!中的指数为奇数，则需要除去if(isExponentOdd(N,p)&&neededPrimes.size()<50)neededPrimes.push_back(p);if(neededPrimes.size()>=50)break;// 最多输出50个}if(neededPrimes.empty()){cout<<"He might be honest.\n";}else{cout<<"He is a liar.\n";for(size_t i=0;i<neededPrimes.size();i++){if(i>0)cout<<' ';cout<<neededPrimes[i];}cout<<'\n';}}}return0;}

总结

本题的关键在于理解费马平方和定理，将一个几何问题转化为数论问题。对于普通整数，直接检查质因数分解；对于阶乘，利用勒让德公式计算质数指数。算法的时间复杂度可以接受，主要优化在于只关注4k+34k+34k+3质数，并使用位运算加速筛法。

通过本题，我们不仅复习了经典的数论定理，还学习了如何高效处理阶乘的质因数分解问题，这对解决其他数论问题也有很好的借鉴意义。