本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
题目链接：HDU4910
正解：线性筛+$Miller-Rabin$
解题报告：
我也是醉了，开始用$Pollard-rho$一直TLE，只好给成线性筛然后除，结果又一直$WA$，突然发现我的预处理只做到了$10^5$然而应该做到$10^6$…
我打了表，发现有一些神奇的规律，首先答案只能是$1$或者$n-1$。
如果$n$的质因子中有超过$2$个$2$，即是$4$的倍数则$ans=1$。
接下来的判断中，$n$是偶数，先把$n$除以二，再判断。
如果$n$有超过$1$个质因子则输出$1$，否则输出$-1$。
考虑范围内的数最多能有$2$个$>$$10^6$的质因子，暴力做就好了。
//It is made by ljh2000
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
using namespace std;
typedef long long LL;
const int MAXN = 1000011;
int prime[MAXN],cnt;
bool vis[MAXN];
inline LL mul(LL x,LL y,LL mod){ LL r=0; while(y>0) { if(y&1) r+=x,r%=mod; x+=x; x%=mod; y>>=1; } return r; }
inline LL fast_pow(LL x,LL y,LL mod){ LL r=1; while(y>0) { if(y&1) r=mul(r,x,mod); x=mul(x,x,mod); y>>=1; } return r; }
inline LL getint(){
LL w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}
inline void init(){
for(int i=2;i<=1000000;i++) {
if(!vis[i]) { prime[++cnt]=i; }
for(int j=1;j<=cnt && prime[j]*i<=1000000;i++) {
vis[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
inline int Miller_Rabin(LL n){
if(n==1) return 0; if(n==2) return 1; if(!(n&1)) return 0;
int T=5,k=0; LL aa,nn=n-1,bb,cc;
while(!(nn&1)) nn>>=1,k++;
while(T--) {
aa=rand()%(n-1)+1;
bb=fast_pow(aa,nn,n);
for(int i=1;i<=k;i++) {
cc=mul(bb,bb,n);
if(cc==1 && bb!=1 && bb!=n-1) return 0;
bb=cc;
}
if(bb!=1) return 0;
}
return 1;
}
inline void work(){
init();
while(1) {
LL n=getint(),m; if(n==-1) break;
bool flag=0; if(n==1 || n==2 || n==4) { printf("%I64d
",n-1); continue; }
if(n%4==0) { printf("1
"); continue; }
m=n; if(m%2==0) m>>=1;
for(int i=1;i<=cnt;i++) {
if(m%prime[i]==0) {
flag=1;
while(m%prime[i]==0) m/=prime[i];
break;
}
}
if(flag==1) {
if(m==1) printf("%I64d
",n-1);
else printf("1
");
}
else {
if(Miller_Rabin(m)) printf("%I64d
",n-1);
else {
LL kai=(LL)sqrt(m);
if(kai*kai==m) printf("%I64d
",n-1);
else printf("1
");
}
}
}
}
int main()
{
work();
return 0;
}
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。