当m取2时，k至少为$\frac{n}{2}$

所以在最优解中每个数被选中的概率至少为$\frac{1}{2}$

每次随机选取一个位置i，计算出其它数与$a_i$的差值，将差值分解质因数

所有质因数中出现次数的最大值加上与$a_i$相等的数的个数就是选取i的情况下的最优解

为了最大化m，需要将所有相同位置的因数乘起来

给每个位置随机一个权值，全部异或起来求出Hash值，排序后扫一遍统计即可

因为$a_i\leq10^7$，所以可以先一遍线性筛求出每个数是被哪个素数筛掉的，这样就可以做到$O(\log n)$分解质因数

 

#include
     
      #include
      
       using namespace std;const int N=100010,M=10000001,P=664600;int n,i,j,x,a[N],b[N],maxv,p[P],tot,ans1,ans2,T,cnt,pos[P],las[P],now,v[M],tmp[32],fac,vis[P];struct PI{  int cnt,hash,num;  PI(){cnt=hash=0;num=1;}  PI(int _cnt,int _hash,int _num){cnt=_cnt,hash=_hash,num=_num;}}pool[P];inline bool cmp(PI a,PI b){return a.hash
       
        ='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}inline void divide(int x,int y){  int i,j,k;  for(i=0;i
        
         k)pool[j].num=k;  }}int main(){  pool[0].hash=-1;  for(read(n);i
         
          maxv)maxv=a[i];  }  for(i=2;i<=maxv;i++){    if(!v[i])p[v[i]=++tot]=i;    for(j=1;j<=tot;j++){      if(i*p[j]>maxv)break;      v[i*p[j]]=j;      if(i%p[j]==0)break;    }  }  for(T=1;T<=4;T++){    for(x=a[rand()%n],i=cnt=now=0;i
          
           x?(a[i]-x):(x-a[i]),b[i]);else cnt++; sort(pool+1,pool+now+1,cmp); for(j=0,i=1;i<=now;i++)if(pool[i].hash^pool[j].hash){ if(j){ if(pool[j].cnt+cnt>ans1)ans1=pool[j].cnt+cnt,ans2=pool[j].num; else if(pool[j].cnt+cnt==ans1&&pool[j].num>ans2)ans2=pool[j].num; } j=i; }else pool[j].num*=pool[i].num; if(pool[j].cnt+cnt>ans1)ans1=pool[j].cnt+cnt,ans2=pool[j].num; else if(pool[j].cnt+cnt==ans1&&pool[j].num>ans2)ans2=pool[j].num; } return printf("%d %d",ans1,ans2),0;}