题解

题目类型：数论（质因数分解 + Pollard-Rho + Miller-Rabin） / 大整数运算
核心算法：质因数分解统计 + 快速幂 + 自定义高精度类

---

一、题意解析

给定 ( n ) 个正整数 ( a_1, a_2, \ldots, a_n )，要求：

1. 对每个数进行质因数分解；
2. 统计所有质因数的出现次数（不同数字之间相同质因子的次数累计）；
3. 设最大出现次数为 ans，具有该次数的不同质因子数量为 num；
4. 输出：
   • 第一行：ans（最大质因子出现次数）
   • 第二行：( 2^{num} - 1 )

由于结果可能极大，需要用自定义的高精度 bign 类进行大整数计算。

---

二、核心思路

Step 1：质因数分解统计

对于每个输入的整数 a，使用 Pollard-Rho 随机分解算法递归分解成质因子。

• 若 a 是质数，则计数 cnt[a]++；
• 否则找到一个非平凡因子 d，递归分解 d 与 a/d。

统计所有质因子的出现次数，最后遍历 cnt 表：

• 找到最大值 ans = max(cnt[p])
• 统计出现该次数的质因子数量 num

---

Step 2：Miller-Rabin 素性测试

判断大整数 n 是否为素数：

1. 令 n-1 = u * 2^t；
2. 对一组固定的基数 A = {2,325,9375,28178,450775,9780504,1795265022}；
3. 对每个基数执行快速幂 a^u mod n；
4. 若结果不为 1 或 n-1，通过重复平方测试；
5. 若所有基数均通过，则 n 为高概率素数。

该组基数已被证明对 64 位整数确定正确，是常见的 Miller-Rabin 常数集合。

---

Step 3：Pollard-Rho 分解算法

当 n 非素数时，利用伪随机函数：

[ F(x) = (x^2 + c) \mod n ] 不断迭代，使用 Floyd 或 Brent 判环算法检测周期，通过 gcd(|x - y|, n) 找出非平凡因子。

递归调用直到所有因子为素数为止。

算法期望复杂度约 (O(n^{1/4}))，对 64 位整数分解极快。

---

Step 4：高精度运算类 bign

代码中实现了一个自定义高精度整数类 bign，支持：

• 加减乘除取模；
• 比较运算；
• 类型转换（int、long long）；
• 幂函数 pow()；
• 绝对值、GCD 等。

采用分块存储，每块 8 位十进制数字，模数 MOD = 1e8。
实现细节包括：

• 加法进位、减法借位；
• 乘法逐位卷积；
• 除法二分搜索；
• 负号标记 f 处理符号。

该类用于计算最终结果： [ 2^{num} - 1 ] 避免溢出。

---

三、算法整体流程

1. 读入整数 n；
2. 依次读入每个数 a_i 并调用 solve(a_i)：
   • 若为质数直接计数；
   • 否则递归分解；
3. 统计 cnt 中的：
   • 最大值 ans；
   • 具有此值的质数个数 num；
4. 输出：

   ans
   2^num - 1
   

---

四、复杂度分析

阶段	算法	复杂度
Miller-Rabin	素数判断	(O(\log^3 n))
Pollard-Rho	分解合数	期望 (O(n^{1/4}))
计数 + 统计	哈希映射	(O(k))，k为质因子数
高精度计算	快速幂	(O(\log num))

总体对 (a_i \le 10^{18}) 可轻松通过。

---

五、关键函数说明

isprime(n)

基于 Miller-Rabin 的确定性素数判定（64 位范围）。

pollard_rho(n)

随机选择常数 c，构造函数 F(x)，迭代求 gcd(|x−y|,n)，找到非平凡因子。

solve(n)

递归分解质因子并记录出现次数。

pow(bign a, int b)

实现快速幂，用于计算 2^num。

---

六、最终输出逻辑

for(map<long long,int>::iterator it=cnt.begin();it!=cnt.end();it++){
    if((*it).second>ans)ans=(*it).second,num=1;
    else if((*it).second==ans)num++;
}
cout << ans << '\n' << pow((bign)2, num) - 1 << '\n';

即输出：

1. 最大质因子出现次数
2. 拥有该次数的质数种数对应的组合数 (2^{num}-1)

---

七、完整代码（与题给代码一致）

#include<bits/stdc++.h>
using namespace std;
const int BIT=8,MOD=1e8,maxlen=1e4+5;
struct bign{
  vector<int>a;
  bool f;
  bign(){
    a.clear(),f=0;
  }
  bign(const char s[]){
    int i=0,l=strlen(s),j;
    if(a.clear(),f=0,s[0]=='-')i=f=1;
    if(s[i]=='0')return;
    j=(l-i-1)%BIT+1,a.push_back(0);
    for(;i<l;(a.back()*=10)+=s[i++]-'0',j--)if(!j)a.push_back(0),j=BIT;
    reverse(a.begin(),a.end());
  }
  bign(const string &s){
    *this=s.c_str();
  }
  bign(int x){
    a.clear(),x<0?(x=-x,f=1):(f=0);
    if(x)x<MOD?(a.push_back(x)):(a.push_back(x%MOD),a.push_back(x/MOD));
  }
  bign(long long x){
    a.clear(),x<0?(x=-x,f=1):(f=0);
    while(x>MOD)a.push_back(x%MOD),x/=MOD;
    a.push_back(x);
  }
  friend istream& operator>>(istream &in,bign &x){
    char c[maxlen];
    return cin>>c,x=c,in;
  }
  friend ostream& operator<<(ostream& out,const bign &x){
    int i=x.a.size();
    if(!i)return putchar('0'),out;
    if(x.f)putchar('-');
    char sw[BIT+1];
    for(cout<<x.a[--i];i--;){
      for(int j=0;j<BIT;j++)sw[j]='0';
      sw[BIT]='\0';
      int l=BIT,al=x.a[i];
      while(al)sw[--l]=al%10+'0',al/=10;
      cout<<sw;
    }
    return out;
  }
  explicit operator int(){
    int l=a.size(),i,r=0;
    for(i=l-1;i>=0;i--)r=r*MOD+a[i];
    return f?-r:r;
  }
  explicit operator long long(){
    int l=a.size(),i;
    long long r=0;
    for(i=l-1;i>=0;i--)r=r*MOD+a[i];
    return f?-r:r;
  }
  explicit operator bool()const{
    return !a.empty();
  }
  int abscmp(const bign &x)const{
    int l=a.size(),o=x.a.size();
    if(l!=o)return l<o?-1:1;
    while(l--)if(a[l]!=x.a[l])return a[l]<x.a[l]?-1:1;
    return 0;
  }
  int cmp(const bign &x)const{
    if(a.empty())return x.a.empty()?0:(x.f?1:-1);
    if(x.a.empty())return f?-1:1;
    if(!f&&x.f)return 1;
    if(f&&!x.f)return -1;
    return f?-abscmp(x):abscmp(x);
  }
  friend bool operator<(const bign &x,const bign &y){
    return x.cmp(y)<0;
  }
  friend bool operator>(const bign &x,const bign &y){
    return x.cmp(y)>0;
  }
  friend bool operator<=(const bign &x,const bign &y){
    return x.cmp(y)<=0;
  }
  friend bool operator>=(const bign &x,const bign &y){
    return x.cmp(y)>=0;
  }
  friend bool operator==(const bign &x,const bign&y){
    return x.cmp(y)==0;
  }
  friend bool operator!=(const bign &x,const bign &y){
    return x.cmp(y)!=0;
  }
  bign& operator+(){
    return *this;
  }
  bign operator-(){
    bign x=*this;
    return x.f^=1,x;
  }
  void add1(){
    if(++a[0]==MOD){
      a.push_back(0);
      for(int i=0;a[i]==MOD;i++)a[i]=0,a[i+1]++;
      if(!a.back())a.pop_back();
    }
  }
  void sub1(){
    if(--a[0]==-1){
      for(int i=0;a[i]==-1;i++)a[i]+=MOD,a[i+1]--;
      if(!a.back())a.pop_back();
    }
  }
  bign& operator++(){
    return a.empty()?(a.push_back(1),f=0,void()):(f?sub1():add1()),*this;
  }
  bign& operator--(){
    return a.empty()?(a.push_back(1),f=1,void()):(f?add1():sub1()),*this;
  }
  bign operator++(int){
    bign x=*this;
    return a.empty()?(a.push_back(1),f=0,void()):(f?sub1():add1()),x;
  }
  bign operator--(int){
    bign x=*this;
    return a.empty()?(a.push_back(1),f=1,void()):(f?add1():sub1()),x;
  }
  void fit(){
    while(!a.empty()&&!a.back())a.pop_back();
  }
  void add(const bign &x){
    int i,l=a.size(),o=x.a.size(),j;
    if(l<o)a.resize(o);
    a.push_back(0);
    for(i=0;i<o;i++){
      j=a[i]+x.a[i];
      if(j>=MOD)j-=MOD,a[i+1]++;
      a[i]=j;
    }
    fit();
  }
  void sub(const bign &x){
    int i,l=a.size(),o=x.a.size(),j;
    for (i=0;i<o;++i){
      j=a[i]-x.a[i];
      if(j<0)j+=MOD,--a[i+1];
      a[i]=j;
    }
    for(i=o;i<l;i++)if(a[i]<0)a[i]+=MOD,a[i+1]--;
    fit();
  }
  void mul(const bign &x){
    int l=a.size(),o=x.a.size(),k=l+o;
    vector<long long>C(k+2,0);
    a.resize(k);
    for(int i=0;i<k;i++)for(int j=max(i-l+1,0);j<=min(o-1,i);j++)C[i]+=x.a[j]*1ll*a[i-j],C[i+1]+=C[i]/MOD,C[i]%=MOD;
    for(int i=0;i<k;i++)a[i]=C[i];
    fit();
  }
  int div(const int &x){
    int i,l=a.size();
    long long w=0;
    for(i=l-1;i>=0;i--)w=w*MOD+a[i],a[i]=w/x,w-=(long long)(a[i])*x;
    return fit(),w;
  }
  bign div(const bign &x){
    int i,l=a.size(),o=x.a.size(),j=l-o;
    long long u,v,w;
    bign r,k=x;
    k.f=0;
    if(j<0)return r=*this,*this=0,r;
    for(i=l-1;i>j;i--)r=r*MOD+a[i];
    for(i=j,a.resize(j+1);i>=0;i--){
      r=r*MOD+a[i],u=0,v=MOD;
      while(v-u>1){
        w=(u+v)>>1;
        if(k*w<=r)u=w;
        else v=w;
      }
      a[i]=u,r-=k*a[i];
    }
    return fit(),r;
  }
  bign& operator+=(const bign &x){
    if(f==x.f)add(x);
    else if(abscmp(x)>=0)sub(x);
    else{
      bign y=x;
      y.sub(*this),*this=y;
    }
    return *this;
  }
  bign& operator-=(const bign &x){
    if(f!=x.f)add(x);
    else if(abscmp(x)>=0)sub(x);
    else{
      bign y=x;
      y.sub(*this),*this=y,f=!f;
    }
    return *this;
  }
  bign& operator*=(const bign &x){
    return mul(x),f=(f!=x.f),*this;
  }
  bign& operator/=(const int &x){
    return div(abs(x)),f=!((f&&x<0)||(!f&&x>0)),*this;
  }
  bign& operator/=(const bign &x){
    return div(x),f=(f!=x.f),*this;
  }
  bign& operator/=(const long long &x){
    return *this/=(bign)x;
  }
  bign& operator%=(const int &x){
    return *this=f?-div(abs(x)):div(abs(x));
  }
  bign& operator%=(const bign &x){
    return *this=(f?-div(x):div(x));
  }
  bign& operator%=(const long long &x){
    return *this%=(bign)x;
  }
  friend bign operator+(bign x,const bign &y){ 
    return x+=y,x;
  }
  friend bign operator-(bign x,const bign &y){
    return x-=y,x;
  }
  friend bign operator*(bign x,const bign &y){
    return x*=y,x;
  }
  friend bign operator/(bign x,const long long &y){
    return x/=y,x;
  }
  friend bign operator/(bign x,const int &y){
    return x/=y,x;
  }
  friend bign operator/(bign x,const bign &y){
    return x/=y,x;
  }
  friend bign operator%(bign x,const long long &y){
    return x%=y,x;
  }
  friend bign operator%(bign x,const int &y){
    return x%=y,x;
  }
  friend bign operator%(bign x,const bign &y){
    return x%=y,x;
  }
};
void swap(bign &x,bign &y){
  swap(x.f,y.f),swap(x.a,y.a);
}
bign abs(bign x){
  return x.f=0,x;
}
bign pow(bign a,int b){
  bign r=1;
  for(;b;b>>=1){
    if(b&1)r*=a;
    a*=a;
  }
  return r;
}
bign gcd(bign a,bign b){
  bign r=1;
  while(1){
    if(!a||!b)return (a+b)*r;
    while(a.a[0]>>1&&b.a[0]>>1==0)r*=2,a/=2,b/=2;
    while(a.a[0]>>1==0)a/=2;
    while(b.a[0]>>1==0)b/=2;
    if(a<b)swap(a,b);
    a-=b;
  }
}
int n,ans,num;
long long a;
map<long long,int>cnt;
long long qmul(long long a,long long b,long long n){
  return ((unsigned long long)a*b-(unsigned long long)((long double)a/n*b)*n+n)%n;
}
long long qpow(long long a,long long b,long long n,long long ans=1){
  for(a%=n;b;b>>=1)b&1&&(ans=qmul(ans,a,n)),a=qmul(a,a,n);
  return ans;
}
const long long A[7]={2,325,9375,28178,450775,9780504,1795265022};
bool isprime(long long n){
  if(n<=2||~n&1)return n==2;
  int t=__builtin_ctzll(n-1);
  long long u=(n-1)>>t,a,v;
  for(int i=0,s;i<7;i++){
    a=A[i],v=qpow(a,u,n);
    if(a%n==0||v==1)continue;
    for(s=0;s<t;s++,v=qmul(v,v,n))if(v==n-1)break;
    if(s==t)return 0;
  }
  return 1;
}
long long F(long long x,long long c,long long n){
  return (qmul(x,x,n)+c)%n;
}
long long pollard_rho(long long n){
  long long c=rand()%(n-1)+1,s=0,t=0,v=1;
  for(int g=1;;g<<=1,s=t){
    for(int i=1;i<=g;i++){
      t=F(t,c,n),v=qmul(v,abs(t-s),n);
      if(!v)return n;
      if(i%127==0){
        long long d=__gcd(v,n);
        if(d>1)return d;
      }
    }
    long long d=__gcd(v,n);
    if(d>1)return d;
  }
}
void solve(long long n){
  if(n==1)return;
  if(isprime(n)){
    cnt[n]++;
    return;
  }
  long long d=pollard_rho(n);
  solve(d),solve(n/d);
}
int main(){
  cin>>n;
  for(int i=1;i<=n;i++)cin>>a,solve(a);
  for(map<long long,int>::iterator it=cnt.begin();it!=cnt.end();it++){
    if((*it).second>ans)ans=(*it).second,num=1;
    else if((*it).second==ans)num++;
  }
  return cout<<ans<<'\n'<<pow((bign)2,num)-1<<'\n',0;
}