题目传送门

本题主要考查 Pollard-Rho 算法。

思路

数据不是很大，所以我们可以使用 Prollard-Rho 算法分解质因数，映射到数组 $S$ 中，很明显 $k$ 的值为 $S$ 数组中出现最多的数的次数，令 $cnt$ 为在 $S$ 数组中与 $k$ 相等的数的个数，则满足条件的 $d$ 的方案数为 $2^{cnt}-1$。$2^{cnt-1}$ 可能会很大，这里需要用高精。

不考虑 $-1$ 对答案的贡献，则剩下的式子为 $2$ 的幂，可以用 long double 存 $2^{cnt-1}$，转成字符串在进行减 1 操作。

对于 Pollard-Rho 算法，这里浅谈一下，本质上是随机化，利用生日悖论来提高算法的正确率。随机选出两个数 $x,y$，两个数的差的绝对值有很大可能为 $N$ 的因子，即 $\gcd(\left|x-y\right|,N)>1$，时间复杂度依旧是很高，可以利用 Floyd 判圈法提升速度。

有以下图：

这也就说明为什么算法名有一个 $\rho$ 了。

贴贴代码

#include <bits/stdc++.h>
#define ll long long
#define Auto map<ll,ll>::iterator
#define lll __int128
using namespace std;
const ll Maxn=610,inf=0x3f3f3f3f;
map<ll,ll>S;
char ans[Maxn];
namespace Math{
	inline ll mul(ll a,ll b,ll p){
		a%=p,b%=p;
		ll c=a*b-(ll)((long double)a*b/p+0.5)*p;
		return c<0?c+p:c;
	}
	inline ll ksm(ll a,ll b,ll Mod)
	{ll z=1;while(b){if(b&1)z=(lll)z*a%Mod;a=(lll)a*a%Mod;b>>=1;}return z;}
	inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
}
using namespace Math;
namespace Miller_Rabin{
	ll Test[11]={0,2,7,41,61};
	inline bool Prime(ll X){
		if(X<2) return false;
		ll k=0,t=X-1;
		while(1^(t&1)) t>>=1,++k;
		for(ll i=1;i<=4;i++){
			if(X==Test[i]) return true;
			ll A=ksm(Test[i],t,X),Next=A;
			for(ll j=1;j<=k;j++){
				Next=mul(A,A,X);
				if(Next==1&&A!=1&&A!=X-1) return false;
				A=Next;
			}
			if(Next!=1) return false;
		}
		return true;
	}
}
using namespace Miller_Rabin;
namespace Pollard_Rho{
	#define Rand(P) (rand()*rand()%(P)+1)
	inline ll PR(ll X,ll Y){
		ll t=0,k=1,v0=Rand(X-1),v1=v0,d,s=1;
		while(true){
			v1=(mul(v1,v1,X)+Y)%X;s=mul(s,abs(v1-v0),X);
			if(!(v1^v0)||!s) return X;
			if(++t==k){if((d=gcd(s,X))^1)return d;v0=v1;k<<=1;}	
		}
	}
	inline void solve(ll X){
		if(X<2) return ;
		if(Prime(X)){S[X]++;return ;}
		ll Y=X;while((Y=PR(X,Rand(X)))==X);
		solve(X/Y);solve(Y);
	}
}
ll m,a,ans1=-inf,cnt;
int main(){
	srand(time(0));
	scanf("%lld",&m);
	for(ll i=1;i<=m;i++) scanf("%lld",&a),Pollard_Rho::solve(a);
	for(Auto it=S.begin();it!=S.end();it++) ans1=max(ans1,it->second);
	for(Auto it=S.begin();it!=S.end();it++) cnt+=(ans1==it->second);
	printf("%lld\n",ans1);
	sprintf(ans,"%.0Lf",powl(2.0L,cnt));
	ans[strlen(ans)-1]--;
	cout<<ans;
	return 0;
}