这个题目巨坑啊。调试的时间加起来绝对超过1天整。
不过终于调试出来了，真心感动地尿流满面啊。
题目的意思是给你一个区间[A,B]，可以从区间里选出任意多个整数，使得这些整数的积是一个不超过 2^126的 平方数。
比赛的时候的想法就基本和题解差不多了，但是依然没有能够A出来。神坑啊。
知道现在才搞定。
首先我们可以知道这个区间的右端点不超过4900，在1-4900里面有70个平方数。所以只要给定的区间包含了一个或多个平方数，我们直接输出最小的那个平方数就可以了哦。这样我们可以保证区间的长度小于139。
但是我们仍然无法圆满地解决这个问题，因为2^138依然是一个巨大的数字，时间和空间都是无法承受的。
再想优化的办法。我们可以发现，有的数字是一定不能选的，那就是区间里仅被含有一次的素数因子，因为只要你选了这个数，无论你接下来怎么选择，都无法凑成一个平方数。（但是值得注意的是，如果区间的一个数含有独特的因子，但是其含有的是该素数因子的平凡的话，也不能被筛去，我就是这里Wa出翔了）
这样我们可以发现我们可以把可选的数字的个数降低到不超过50。
接下来还有最后一个优化，题目里面说过最后的那个平方根不会超过2^63，这样等于是那个平凡数不会超过2^126，这样我们应该选择的数的个数就只有12个左右了。
（可以这样理解，前面的平方数之间的距离比较窄，所以个数不会多；后面的平方数之间距离虽然比较宽，但是本身比较大，所以也不会选择太多，这样考虑就知道了所有的个数不超过12个咯）。
有了这个我们就可以逐步枚举所有的组合情况了，（注意从个数少的枚举到个数多的，同时注意数小的数要先进行判定，这样保证找到的第一个可行解是最小解——这里题解写的是要用单调队列优化，但是我是这样做的，先保存所有选择一个的情况，然后判断并且由此推出所有选择两个的情况 ，每次对于当前因子数的所有数都处理完成后，对下面一列进行一次排序就好了——单调队列不会写T_T 。这样就保证了第一次找到的解是最小解了。）
其实在实现的过程中有好多的小细节，比如位运算的时候，1要写成（ll）1，不然就等着爆吧。还有对于两种组合后积大小的比较我是依靠一个double来比较的，个人认为这个方法略怂，但是还挺管用，嘿嘿。
详细的就见代码吧！
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 #define ll unsigned long long 7 #define maxQ 1000000//理论上来说要开的大一些 8 #define maxn 4920 9 using namespace std; 10 11 struct node{ 12 double tot; 13 ll id; 14 }cur,p; 15 16 vector<int> vet[maxn+10]; 17 18 int prim[maxn+10],f1[maxn+10],Pnum,num[1000]; 19 int N[2],t[2],s[2],A,B,tim,ans[45],pos,cas=0; 20 bool b[maxn+10],flag[maxn+10]; 21 node Q[2][maxQ]; 22 ll total; 23 24 bool cmp(node n1,node n2) 25 { 26 return n1.tot<n2.tot; 27 } 28 29 void getprim() 30 { 31 for (int i=2; i<maxn; i++) 32 { 33 if (b[i]) continue; 34 prim[++Pnum]=i,f1[i]=Pnum; 35 for (int j=i+i; j<maxn; j+=i) b[j]=true; 36 } 37 for (int i=2; i<4901; i++) 38 { 39 int k=i; 40 for (int j=1; prim[j]<=k; j++) 41 while (k%prim[j]==0) vet[i].push_back(prim[j]),k/=prim[j]; 42 } 43 } 44 45 void select_use_element() 46 { 47 int beg; 48 for (int i=1; i<=Pnum; i++) 49 { 50 //if (prim[i]<50) continue; 51 //if (A%prim[i]==0) tim=1; else tim=0; 52 if (A%prim[i]==0) beg=A; 53 else beg=(A-A%prim[i])+prim[i]; 54 if (B>=beg) tim=(B-beg)/prim[i]+1; 55 else tim=0; 56 if (tim>1) continue; 57 //if (prim[i]<50) continue; 58 for (int j=prim[i]; j<maxn; j+=prim[i]) flag[j]=true; 59 //if (prim[i]<=65) continue; 60 for (int j=prim[i]*prim[i]; j<maxn; j+=prim[i]*prim[i]) flag[j]=false; 61 } 62 tim=0; 63 for (int i=A; i<=B; i++) if (!flag[i]) num[++tim]=i;//,cout<<i<<' ';//tim最终表示有多少个有用的数。 64 //cout<<" tim : "<<++cas<<' '<<tim<<" "<<A<<' '<<B<<endl; 65 } 66 67 void output_digit(ll x) 68 { 69 while (x) cout<<(x&1),x>>=1; cout<<endl; 70 } 71 72 bool check(int x,int y) 73 { 74 p=Q[x][y]; 75 memset(ans,0,sizeof ans); 76 for (int i=1; i<=tim; i++) 77 if ((p.id)&((ll)1<<(i-1))) 78 { 79 for (unsigned k=0; k<vet[num[i]].size(); k++) 80 ans[f1[vet[num[i]][k]]]++; 81 } 82 //for (int i=1; i<45; i++) cout<<ans[i]<<' '; cout<<endl; 83 for (int i=1; i<45; i++) 84 { 85 if (ans[i]%2!=0) 86 { 87 ans[0]=-1; 88 return false; 89 } 90 } 91 //output_digit(p.id); 92 ans[0]=1; 93 return true; 94 } 95 96 void queue_operation() 97 { 98 N[1]=1; s[1]=1,t[1]=0; 99 p.id=0,p.tot=0; 100 for (int i=1; i<=tim; i++) 101 { 102 cur.tot=num[i],cur.id=((ll)1<<(i-1)); 103 Q[1][++t[1]]=cur; 104 } 105 sort(Q[1]+1,Q[1]+1+t[1],cmp); 106 int now=1,next; 107 while (N[now]<=12) 108 { 109 //cout<<"Nnow: "<<N[now]<<' '<<t[now]<<endl; 110 next=1-now; 111 s[next]=1,t[next]=0,N[next]=N[now]+1; 112 for (int i=s[now]; i<=t[now]; i++) 113 { 114 if (check(now,i)) return; 115 cur=Q[now][i]; 116 for (pos=1; ((ll)1<<(pos-1))<=cur.id; pos++) ; 117 //output_digit(cur.id); 118 for (int j=pos; j<=tim; j++) 119 if (((cur.id)&((ll)1<<(j-1)))==0) 120 { 121 t[next]++;//=(t[next]+1)%maxQ; 122 p.tot=cur.tot*num[j]; 123 p.id=(cur.id)|((ll)1<<(j-1)); 124 Q[next][t[next]]=p; 125 } 126 } 127 sort(Q[next]+1,Q[next]+1+t[next],cmp); 128 swap(now,next); 129 } 130 } 131 132 void output_ans() 133 { 134 if (ans[0]==-1) { cout<<"none "; return; } 135 total=1; 136 for (int i=1; i<45; i++) 137 for (int j=1; j+j<=ans[i]; j++) total*=prim[i]; 138 cout<<total<<endl; 139 } 140 141 int main() 142 { 143 //freopen("C:/Users/Administrator/Desktop/data.in","r",stdin); 144 //freopen("C:/Users/Administrator/Desktop/data.out","w",stdout); 145 getprim(); 146 while (cin>>A>>B) 147 { 148 memset(ans,0,sizeof ans); 149 ans[0]=-1; 150 for (tim=1; tim*tim<=B; tim++) if (tim*tim>=A) break; 151 if (tim*tim<=B) 152 { 153 cout<<tim<<endl; 154 continue; 155 } 156 memset(flag,false,sizeof flag); 157 select_use_element(); 158 queue_operation(); 159 output_ans(); 160 } 161 return 0; 162 }