这题意思很简单。求一棵树里面的一条路径，使得其异或权(就是将路径里面所有边的权值异
或起来)最大。
这个题有两步。第一步是假定根为节点0，求出根到其它节点的异或距离，保存在数组xor里面，
这个dfs一下即可。然后，用xor[i]^xor[j]就能代表节点i到节点j的路径。这个结论可以这么看。
如果，i和j之间的路径经过根节点，那么上面的结论肯定是正确的。如果，该路径不经过根，那么
xor[i]和xor[j]必定保护从根到某个节点的相同的一段子路径，根据异或的性质，这段子路径会
被消掉，所以这个结论也是这确的。。。
第二步就是枚举，xor[i]^xor[j]使得结果最大了。如果直接暴力，平方的算法肯定会超时的。
由于每个值可以表示成2进制，如果把其它xor值都保存在字典树里面，用当前的xor[i]去字典树
里面，一遍就可以找到异或最大值。
另外，由于树的点数太多，只能用邻接表，用vector模拟邻接表果断超时了。。。
改成静态链表才过。。。
代码如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 100010;
int nXor[MAX];
bool bVis[MAX];
int nFirst[MAX];
struct Edge
{
int nE;
int nW;
int nNext;
};
Edge egs[MAX * 2];
struct Node
{
Node* pSons[2];
};
Node nodes[MAX * 32];
Node* pRoot = &nodes[0];
int nNew;
void GetBCode(
int nL,
int* nBCode,
int& nLen)
{
nLen = 0;
while (nLen <= 30)
{
nBCode[nLen++] = nL % 2;
nL >>= 1;
}
reverse(nBCode, nBCode + nLen);
}
void Insert(
int nL)
{
int nLen = 0;
int i = 0;
int nBCode[32];
GetBCode(nL, nBCode, nLen);
Node* pNode = pRoot;
while (i < nLen)
{
if (pNode->pSons[nBCode[i]])
{
pNode = pNode->pSons[nBCode[i]];
}
else {
memset(nodes + nNew, 0,
sizeof(nodes[nNew]));
pNode->pSons[nBCode[i]] = nodes + nNew;
pNode = nodes + nNew;
++nNew;
}
++i;
}
}
int FindMax(
int nL)
{
int nLen = 0;
int nAns = 0;
int i = 0;
int nBCode[32];
Node* pNode = pRoot;
GetBCode(nL, nBCode, nLen);
while (i < nLen)
{
int nBest = (nBCode[i] == 0 ? 1 : 0);
int nBad = (nBCode[i] == 0 ? 0 : 1);
if (pNode->pSons[nBest])
{
nAns = 2 * nAns + nBest;
pNode = pNode->pSons[nBest];
}
else if (pNode->pSons[nBad])
{
nAns = 2 * nAns + nBad;
pNode = pNode->pSons[nBad];
}
else break;
++i;
}
return nAns ^ nL;
}
void Dfs(
int nV,
int nL)
{
nXor[nV] = nL;
bVis[nV] =
true;
for (
int e = nFirst[nV]; e != -1; e = egs[e].nNext)
{
if (!bVis[egs[e].nE])
{
Dfs(egs[e].nE, nL ^ egs[e].nW);
}
}
}
int main()
{
int nN;
int nU, nV, nW;
while (scanf("%d", &nN) == 1)
{
for (
int i = 0; i < nN; ++i) nFirst[i] = -1;
for (
int i = 1, j = 0; i < nN; ++i)
{
scanf("%d%d%d", &nU, &nV, &nW);
egs[j].nE = nV;
egs[j].nW = nW;
egs[j].nNext = nFirst[nU];
nFirst[nU] = j++;
egs[j].nE = nU;
egs[j].nW = nW;
egs[j].nNext = nFirst[nV];
nFirst[nV] = j++;
}
memset(bVis,
false,
sizeof(
bool) * nN);
Dfs(0, 0);
memset(&nodes[0], 0,
sizeof(Node));
nNew = 1;
int nAns = 0;
for (
int i = 0; i < nN; ++i)
{
nAns = max(nAns, FindMax(nXor[i]));
Insert(nXor[i]);
}
printf("%d\n", nAns);
}
return 0;
}
这是并查集最后一题，据说也是最经典的一题。经常前面几题的训练，这题的思路很快
就能想出来了。只需要对每个节点附加一个信息表示离根节点的距离，并且距离是模3循环的。
注意合并时候保持距离变化的正确性。而且合并有2种情况，距离相同合并和距离不同合并。
分别对应于题目描述中的1和2操作。
关键还是FindSet里面对距离nDis数组里面的修改，前面一直写错这个，wa了好几次，还是
看队友代码才一眼发现我又把这里写错了。。。当前距离的更新还是等于当前距离加上前一个
节点的距离再模3，类似于前面几题的更新方法。
这种将有关系的节点放在一个并查集里面，再给每个节点附加其它信息描述其它关系的做法，
确实比较有效。。。并查集是应用于不相交集合的数据结构，看来某个时候却有妙用啊。。。
代码如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
using namespace std;
const int MAX = 50010;
int nN, nK;
int nSets[MAX];
int nDis[MAX];
void MakeSets(
int nN)
{
for (
int i = 1; i <= nN; ++i)
{
nSets[i] = i;
nDis[i] = 0;
}
}
int FindSet(
int nI)
{
if (nSets[nI] != nI)
{
int nPre = nSets[nI];
nSets[nI] = FindSet(nSets[nI]);
nDis[nI] = (nDis[nPre] + nDis[nI]) % 3;
}
return nSets[nI];
}
int main()
{
int nAns = 0;
int nOper, nX, nY;
scanf("%d%d", &nN, &nK);
MakeSets(nN);
while (nK--)
{
scanf("%d%d%d", &nOper, &nX, &nY);
if (nX > nN || nY > nN || nOper == 2 && nX == nY)
{
++nAns;
}
else {
if (nOper == 1)
{
int nA = FindSet(nX);
int nB = FindSet(nY);
if (nA == nB)
{
if (nDis[nX] != nDis[nY])
{
++nAns;
}
}
else {
nSets[nB] = nA;
nDis[nB] = (nDis[nX] - nDis[nY] + 3) % 3;
}
}
else {
int nA = FindSet(nX);
int nB = FindSet(nY);
if (nA == nB)
{
if ((nDis[nX] + 1) % 3 != nDis[nY])
{
++nAns;
}
}
else {
nSets[nB] = nA;
nDis[nB] = (nDis[nX] + 1 - nDis[nY] + 3) % 3;
}
}
}
}
printf("%d\n", nAns);
return 0;
}
也是个题意比较奇葩的题目。有2个操作，1个是把一个元素所在的栈，放到另外1个元素所在
的栈上面。另外一个操作是统计某个元素下面有多少个元素(当然是在同一个栈中）。
貌似，需要记录每个元素下面的元素是什么了，既然要记录这个就不能用并查集的路径压缩了。
不压缩路径的话，肯定会超时的。怎么办了。。。
其实，可以这么考虑，以每个栈的栈底元素作为并查集的代表元素。压缩路径后，每个元素或者
是根元素或者其父亲元素就是根元素。所以，另外对每个节点附加个信息代表该节点的高度，栈底
元素高度为0。再附加个信息代表每个并查集元素总数目，这样就可以在合并集合时候修改信息，
并且压缩路径也能保证答案正确。。。
代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <
string.h>
#include <algorithm>
using namespace std;
const int MAX = 30010;
int nSets[MAX];
int nNum[MAX];
int nRank[MAX];
void MakeSets(
int nN)
{
for (
int i = 0; i < nN; ++i)
{
nSets[i] = i;
nNum[i] = 1;
nRank[i] = 0;
}
}
int FindSet(
int nI)
{
if (nSets[nI] != nI)
{
int nPre = nSets[nI];
nSets[nI] = FindSet(nSets[nI]);
nRank[nI] += nRank[nPre];
}
return nSets[nI];
}
void Move(
int nX,
int nY)
{
int nA = FindSet(nX);
int nB = FindSet(nY);
//printf("nA:%d,nB:%d\n", nA, nB);
if (nA != nB)
{
nSets[nA] = nB;
nRank[nA] += nNum[nB];
nNum[nB] += nNum[nA];
}
}
int main()
{
int nP;
char szOper[10];
int nX, nY;
scanf("%d", &nP);
MakeSets(MAX);
while (nP--)
{
scanf("%s", szOper);
if (szOper[0] == 'M')
{
scanf("%d%d", &nX, &nY);
Move(nX, nY);
}
else {
scanf("%d", &nX);
FindSet(nX);
printf("%d\n", nRank[nX]);
}
}
return 0;
}
并查集应用的变形。题目意思是一个图中，只有上下左右四个方向的边。给出这样的一些边，
求任意指定的2个节点之间的距离。
有可能当前给出的信息，没有涉及到要求的2个节点，或者只涉及到了1个节点，那么肯定
无法确定它们的距离。或者根据已经给出的边只知道这2个节点在不同的联通分量里面，那么其
距离也是无法确定的，根据题目要求，输出-1。
问题是如果能够确定它们在一个联通分量里面，如何确定它们的距离了。
这个题的关键在于，只有上下左右四个方向的边，假设每个节点都有一个坐标的话，那么它们
相对于代表该联通分量节点的坐标肯定是固定的，那么就不需要考虑图里面有环之类的情况了。
这样就可以很方便的应用并查集来解了。
利用并查集，给每个节点附加其它信息，即相对于代表该并查集的节点的坐标（x，y）。
在FindSet里面求出坐标，在UnionSet里面修改合并后新加入的另外一个集合的根节点的坐标即可。
代码如下：
#include <stdio.h>
#include <
string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
const int MAX_N = 40010;
int nN, nM;
int nSets[MAX_N];
int nX[MAX_N];
int nY[MAX_N];
char szInput[MAX_N][100];
void MakeSets(
int nNum)
{
for (
int i = 0; i < nNum; ++i)
{
nSets[i] = i;
nX[i] = nY[i] = 0;
}
}
int FindSets(
int nI)
{
if (nSets[nI] != nI)
{
int nPre = nSets[nI];
nSets[nI] = FindSets(nSets[nI]);
nX[nI] += nX[nPre];
nY[nI] += nY[nPre];
}
return nSets[nI];
}
void UnionSets(
int nBeg,
int nEnd,
int dx,
int dy)
{
int nA = FindSets(nBeg);
int nB = FindSets(nEnd);
if (nA != nB)
{
nSets[nB] = nA;
//把集合B合并到集合A中
nX[nB] = nX[nBeg] + dx - nX[nEnd];
//因为方向逆过来了,所以是减去
nY[nB] = nY[nBeg] + dy - nY[nEnd];
}
}
int main()
{
int nBeg, nEnd, nL;
char szDir[10];
while (scanf("%d%d%*c", &nN, &nM) == 2)
{
MakeSets(nN);
for (
int i = 0; i < nM; ++i)
{
fgets(szInput[i], 100, stdin);
}
int nK;
int nF1, nF2, nI;
scanf("%d", &nK);
int nCur = 0;
while (nK--)
{
scanf("%d%d%d", &nF1, &nF2, &nI);
for (
int i = nCur; i < nI; ++i)
{
sscanf(szInput[i], "%d%d%d%s", &nBeg,
&nEnd, &nL, szDir);
int dx = 0, dy = 0;
switch (szDir[0])
{
case 'N': dy += nL;
break;
case 'S': dy -= nL;
break;
case 'E': dx += nL;
break;
case 'W': dx -= nL;
break;
}
UnionSets(nBeg, nEnd, dx, dy);
}
nCur = nI;
if (FindSets(nF1) != FindSets(nF2))
{
printf("-1\n");
}
else {
printf("%d\n", abs(nX[nF1] - nX[nF2])
+ abs(nY[nF1] - nY[nF2]));
}
}
}
return 0;
}
并查集应用的变形。
给出的是2个节点是敌对关系的信息，最后询问任意2个节点的关系。根据这些信息，
节点之间可能是敌对的，也可能不是的（因为敌人的敌人就是朋友），也可能给出的
信息根本描述不了它们的关系。
看起来跟原始的并查集应用差远了。。。
有个比较直接的做法，那么就是把不在一个集合的节点直接用并查集合并在一起。这样的话，
如果询问的2个节点在同一个并查集里面，那么它们之间的关系是确定的，否则无法确定它们的
关系。
现在还有一个问题是，在同一个并查集里面的2个节点是敌对关系还是朋友关系。。。
可以给每个节点另外附加个信息，记录其距离并查集根节点的距离。如果，询问的2个节点距离
其根节点的距离都是奇数或者都是偶数，那么这2个节点是朋友关系，否则是敌对关系。。。
代码如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
using namespace std;
const int MAX_N = 100010;
int nSets[MAX_N];
int nDis[MAX_N];
int nN, nM;
void MakeSets(
int nNum)
{
for (
int i = 0; i < nNum; ++i)
{
nSets[i] = i;
nDis[i] = 0;
}
}
int FindSet(
int nI)
{
if (nSets[nI] != nI)
{
int nPre = nSets[nI];
nSets[nI] = FindSet(nSets[nI]);
nDis[nI] = (nDis[nI] + nDis[nPre]) % 2;
}
return nSets[nI];
}
void UnionSet(
int nI,
int nJ)
{
int nA = FindSet(nI);
int nB = FindSet(nJ);
if (nA != nB)
{
nSets[nA] = nB;
nDis[nA] = (nDis[nI] + nDis[nJ] + 1) % 2;
}
}
int main()
{
int nT;
scanf("%d", &nT);
while (nT--)
{
scanf("%d%d", &nN, &nM);
MakeSets(nN);
char szOper[10];
int nA, nB;
while (nM--)
{
scanf("%s%d%d", szOper, &nA, &nB);
if (szOper[0] == 'D')
{
UnionSet(nA, nB);
}
else {
int nX = FindSet(nA);
int nY = FindSet(nB);
if (nX == nY)
{
if (nDis[nA] == nDis[nB])
{
printf("In the same gang.\n");
}
else {
printf("In different gangs.\n");
}
}
else {
printf("Not sure yet.\n");
}
}
}
}
return 0;
}
此题本来模拟即可，但是注意有容易出错的地方。
这题主要是可以用中国剩余定理来做。
根据题意可以抽象出这样的模型。给出三个数A,B,C分别是模23,28,33后的余数，求最小的数字
使得其模23,28,33分别为A,B,C，并且要大于给定的数字D。
中国剩余定理很好的解决了这种余数问题。令模数为Ni,余数为Ai,设Mi = N1*N2*...*Ni-1*Ni+1*...*Nn，
那么答案一定满足形式ans =
ΣAi*Mi*(Mi对Ni的乘法逆) % N。(N为所有Ni的乘积)。
很明显，由于ans的第i项有Mi因子，所以模N1-Ni-1和Ni+1-Nn肯定是0，而Ai*Mi*(Mi对Ni的乘法逆) %Ni
就是Ai。这样就满足了要求。
代码如下：
#include <stdio.h>
#include <algorithm>
#include <
string.h>
#include <vector>
using namespace std;
int Egcd(
int nN,
int nM,
int& nX,
int& nY)
{
if (nM == 0)
{
nX = 1, nY = 0;
return nN;
}
int nRet = Egcd(nM, nN % nM, nX, nY);
int nT = nX;
nX = nY;
nY = nT - (nN / nM) * nY;
return nRet;
}
int main()
{
int nA, nB, nC, nD;
int nDays = 21252;
int nCase = 1;
while (scanf("%d%d%d%d", &nA, &nB, &nC, &nD),
nA != -1 || nB != -1 || nC != -1 || nD != -1)
{
int nFirst = 0;
nA %= 23;
nB %= 28;
nC %= 33;
int nM1= 28 * 33, nM2 = 23 * 33, nM3 = 23 * 28;
int nN1, nN2, nN3, nTemp;
Egcd(23, nM1, nTemp, nN1);
Egcd(28, nM2, nTemp, nN2);
Egcd(33, nM3, nTemp, nN3);
nFirst = (nA * nM1 * nN1 + nB * nM2 * nN2 + nC * nM3 * nN3) % nDays;
while (nFirst <= nD)nFirst += nDays;
printf("Case %d: the next triple peak occurs in %d days.\n",
nCase++, nFirst - nD);
}
return 0;
}
这个题是求一个字符串的最小重复单元的重复次数，那么求出最小重复单元的长度即可。
这个题有3种方法，方法一：直接枚举长度为[1,len/2]内的子串，暴力就过了。方法二：
将原串重复一次形成一个新串，用原串去匹配新串，但是得从第二个位置开始匹配，第一次
成功匹配的位置减一就代表最小重复单元的长度。方法三：利用kmp的next函数，如果len
能够整除len-next[len]，那么len-next[len]就代表最小重复单元的长度。
方法一明显是对的，数据不强的情况下就能水过了。方法二也不是那么容易想到的，不过
将原串扩展为2倍的做法也不是太奇葩，比如判断2个循环串是否相等就可以用这个办法做。
方法三就比较难理解了。
方法三的理解：
next[len]代表的是str的最长前缀(使得这个前缀与同样长度的后缀相等)的长度。所谓的next
数组就是长度为1-len的str的满足上述描述的最长前缀的长度。如果len是len-next[len]的倍数，
假设m = len-next[len] ，那么str[1-m] = str[m-2*m]，以此类推下去，m肯定是str的最小
重复单元的长度。假如len不是len-next[len]的倍数， 如果前缀和后缀重叠，那么最小重复单元
肯定str本身了，如果前缀和后缀不重叠，那么str[m-2*m] != str[len-m,len]，所以str[1-m]
!= str[m-2*m] ,最终肯定可以推理出最小重复单元是str本身，因为只要不断递增m证明即可。
方法三的代码如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
using namespace std;
char szStr[1000010];
int nNext[1000010];
void GetNext(
char* szStr,
int nLen,
int* nNext)
{
nNext[0] = -1;
for (
int i = 1, j = -1; i < nLen; ++i)
{
while (j > -1 && szStr[i] != szStr[j + 1])
{
j = nNext[j];
}
if (szStr[i] == szStr[j + 1])
{
++j;
}
nNext[i] = j;
}
}
int main()
{
while (scanf("%s", szStr), strcmp(szStr, "."))
{
int nLen = strlen(szStr);
GetNext(szStr, nLen, nNext);
if (nLen % (nLen - nNext[nLen - 1] - 1))
{
printf("1\n");
}
else {
printf("%d\n", nLen / (nLen - nNext[nLen - 1] - 1));
}
}
return 0;
}
裸的字符串匹配，子串最长10,000，母串最长
1,000,000。
求子串在母串中出现的次数。
如果子串长度较小，那么直接RK匹配即可，hash值相同时候，直接比较字符串是否相同。
但是这个题的子串太长了，还比较字符串会超时，如果不比较字符串理论上是错误的，虽然
出错的概率很小，而且概率还是跟模数的选择以及运算时候是否溢出有关。
刚开始用了int，发现一直wa了，估计就是运算时候就超int了，取模没起到作用。模数的选
择能够提高正确率。Rabin-Karp 字符串匹配虽然比较好写，也很容易理解，但是适用情况感
觉不是很广，比如子串太长了，处理就麻烦了，舍弃子串比较也不是很好。
但是子串不长的话，Rabin-Karp 字符串匹配还是很不错的。
相比而言，这个题用kmp应该会好很多。
代码如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
using namespace std;
typedef
long long INT;
char szStrM[1000010];
char szStrS[10010];
const INT MOD = 16381 * 4733 + 1;
int main()
{
int nT;
scanf("%d", &nT);
while (nT--)
{
scanf("%s%s", szStrS, szStrM);
INT nMatch = szStrS[0] - 'A';
INT nPowN = 1;
int nSizeS = 1;
char* pszStr = szStrS + 1;
while (*pszStr)
{
nMatch = (26 * nMatch + *pszStr - 'A') % MOD;
nPowN = (nPowN * 26) % MOD;
++nSizeS;
++pszStr;
}
//prINTf("match:%d\n", nMatch);
int nSizeM = strlen(szStrM);
INT nKey = 0;
for (
int i = 0; i < nSizeS; ++i)
{
nKey = (26 * nKey + szStrM[i] - 'A') % MOD;
}
//prINTf("key:%d\n", nKey);
int nAns = 0;
for (
int i = 0; i <= nSizeM - nSizeS; ++i)
{
//prINTf("key:%d\n", nKey);
if (nKey == nMatch)
// && memcpy(szStrS, szStrM + i, nSizeS) == 0)
{
++nAns;
}
nKey = (26 * (nKey - nPowN * (szStrM[i] - 'A')) % MOD
+ szStrM[i + nSizeS] - 'A') % MOD;
nKey = (nKey + MOD) % MOD;
}
printf("%d\n", nAns);
}
return 0;
}
这个题是求一个字符串里面出现了多少个长度为N的不同子串，同时给出了母串里面不同字符
的个数NC。
保存子串到set里面直接暴力肯定超时了。这个题有个利用字符串hash的解法，虽然理论上有
bug，但是能过这个题。
利用给出的NC，对长度为N的字符串，将其当作NC进制的数字，求出其值，对值进行hash，
求出不同的hash位置个数。
这个算法其实类似于Karp-Rabin字符串匹配算法。不过，Karp-Rabin算法做了点改进，对
进制为D的字符串求值的时候为了防止溢出会模一个素数，而且不会每次都迭代求下一个子串的
值，而是从当前子串的值直接递推出下一个字符的值。怎么递推了，其实很简单，就是当前值去
掉最高位再乘以D(相当于左移一位,不过是D进制的，不能直接用<<符号)，再加上新的最低位。
Karp-Rabin算法应该主要在于设计出合理的hash算法，比如，用取模hash函数的话，得保
证hash表足够大，否则冲突太多，速度就不会怎么好了。比如这个题，hash表小了就AC不了了。
代码如下：
#include <stdio.h>
#include <string.h>
const int MAX = 13747347;
int nHash[MAX];
char szStr[17000001];
int nN, nNC;
int nW[200];
void Insert(int nKey)
{
int nPos = nKey;
while (nHash[nPos] != -1 && nHash[nPos] != nKey)
{
nPos = (nPos + 1) % MAX;
}
nHash[nPos] = nKey;
}
bool Find(int nKey)
{
int nPos = nKey;
while (nHash[nPos] != -1 && nHash[nPos] != nKey)
{
nPos = (nPos + 1) % MAX;
}
return nHash[nPos] != -1;
}
int main()
{
while (scanf("%d%d%s", &nN, &nNC, szStr) == 3)
{
memset(nW, 0, sizeof(nW));
memset(nHash, -1, sizeof(nHash));
int nNum = 0;
int nSize = 0;
for (char* pszStr = szStr; *pszStr; ++pszStr)
{
if (!nW[*pszStr])
{
nW[*pszStr] = ++nNum;
}
++nSize;
}
int nKey = 0;
int nAns = 0;
int nPowN = 1;
for (int j = 0; j < nN; ++j)
{
nKey = (nKey * nNC + nW[szStr[j]]) % MAX;
nPowN *= nNC;
}
nPowN /= nNC;
if (!Find(nKey))
{
Insert(nKey);
nAns++;
}
for (int i = nN; i < nSize; ++i)
{
nKey = (nNC * (nKey - nPowN * nW[szStr[i - nN]])
+ nW[szStr[i]]) % MAX;
nKey = (nKey + MAX) % MAX;
if (!Find(nKey))
{
Insert(nKey);
nAns++;
}
}
printf("%d\n", nAns);
}
return 0;
}
代码如下：
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef unsigned long long LL;
#define MAX (5000000)
bool bPrime[MAX];
void InitPrime()
{
int nMax = sqrt((double)MAX) + 1;
bPrime[0] = bPrime[1] = true;
for (int i = 2; i <= nMax; ++i)
{
if (!bPrime[i])
{
for (int j = 2 * i; j < MAX; j += i)
{
bPrime[j] = true;
}
}
}
}
LL multAndMod(LL a, LL b, LL n)
{
LL tmp = 0;
while (b)
{
if(b & 1)
{
tmp = (tmp + a) % n;
}
a = (a << 1) % n;
b >>= 1;
}
return tmp;
}
//计算a^u%n
LL ModExp(LL a, LL u, LL n)
{
LL d = 1;
a %= n;
while (u)
{
if (u & 1)
{
d = multAndMod(d, a, n);
}
a = multAndMod(a, a, n);
u >>= 1;
}
return d % n;
}
//判断nN是不是合数
bool Witness(LL a, LL nN)
{
LL u = nN - 1, t = 0;//将nN-1表示为u*2^t
while (u % 2 == 0)
{
t++;
u >>= 1;
}
LL x0 = ModExp(a, u, nN);//x是a^u
LL x1;
for (int i = 1; i <= t; ++i)
{
x1 = multAndMod(x0, x0, nN);
if (x1 == 1 && x0 != nN - 1 && x0 != 1)
{
return true;
}
x0 = x1;
}
if (x1 != 1)
{
return true;
}
return false;
}
//素数测试
bool MillerRabin(LL nN)
{
//if (nN < MAX)return !bPrime[nN];
const int TIME = 10;
for (int i = 0; i < TIME; ++i)
{
LL a = rand() % (nN - 1) + 1;
if (Witness(a, nN))
{
return false;
}
}
return true;
}
LL gcd(LL a, LL b)
{
if (a < b)swap(a, b);
while (b)
{
LL t = a;
a = b;
b = t % b;
}
return a;
}
//启发式寻找nN的因子
LL PollardRho(LL n, LL c)
{
LL i = 1, t = 2;
LL x, y;
LL ans;
srand(time(NULL));
y = x = rand() % n;
while(1)
{
i++;
x = (multAndMod(x, x, n) + c) % n;
ans = gcd(y - x, n);
if(ans > 1 && ans < n)
return ans;
if(x == y)
return n;
if(t == i)
{
y = x;
t <<= 1;
}
}
}
LL FindMin(LL nN, LL c)
{
//printf("nN:%I64u\n", nN);
if (MillerRabin(nN) || nN <= 1)
{
return nN;
}
LL p = nN;
while (p >= nN) p = PollardRho(p, c--);
if (p > 1)
p = FindMin(p, c);//分解p的最小因子
if (p < nN)
{
LL q = nN / p;
q = FindMin(q, c);//找到q的最小因子
p = min(p, q);
}
return p;
}
int main()
{
int nTest;
srand(time(NULL));
//InitPrime();
scanf("%d", &nTest);
while (nTest--)
{
LL nN;
scanf("%I64u", &nN);
if (nN > 2 && nN % 2 == 0)
{
printf("2\n");
}
else if (nN == 2 || MillerRabin(nN))
{
printf("Prime\n");
}
else
{
printf("%I64u\n", FindMin(nN, 181));
}
}
return 0;
}