自动搬运

查看原文

来自洛谷，原作者为

	skylee **

搬运于2025-08-24 21:49:34，当前版本为作者最后更新于2018-07-13 13:05:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[POI2010]Divine Divisor

题目大意：

给你$m(m\le600)$个数$a_i(a_i\le10^{18})$。$n=\prod a_i$。现在要你找到一个最大的$k$使得$\exists d\ne1,d^k|n$，并求出有多少$d$满足这样的条件。

思路：

首先线性筛预处理出$10^6$以内的所有质数，用这些质数除$a_i$，剩下的$a_i$分为以下$4$种情况：

1. $a_i=1$，表示$a_i$的所有素数均被找出。
2. $a_i=p^2$，可以判断$\lfloor\sqrt{a_i}\rfloor$是否等于$\lceil\sqrt{a_i}\rceil$，是的话就说明这是两个$>10^6$的质数平方。
3. $a_i=p$，可以使用Miller-Rabin算法判断是否为质数。
4. $a_i=pq$，对于这样的数，可以与其它所有数求一遍$\gcd$。若$\gcd\ne1$就说明我们成功分解了它的质因数。否则虽然我们不能知道它的质因数到底是什么，但是我们可以知道它与其它数没有共同的质因数，因此我们只需要统计出现的次数，而不需要关心其具体数值。

对于每个质数，我们统计其出现次数$cnt[i]$。第一个答案就是$\max\{cnt[i]\}$。若有$k$个质数的出现次数为$\max\{cnt[i]\}$，则第二个答案就是$2^k-1$。

由$k$可能会很大，需要写高精度。

但是我们可以注意到,若不考虑$-1$，答案就是$2$的幂。用浮点数来储存不会丢失精度，且$-1$后不会发生退位。因此可以先用浮点数计算$2^k$，转成字符串，再在最后一位$-1$。

源代码：

#include<map>
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<algorithm>
typedef long long int64;
typedef __int128 int128;
inline int64 getint() {
	register char ch;
	while(!isdigit(ch=getchar()));
	register int64 x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return x;
}
const int M=601,LIM=1e6+1,P=78499;
bool vis[LIM];
int p[P],b[M];
int64 a[M];
std::map<int64,int> cnt,cnt2;
inline void sieve() {
    vis[1]=true;
    for(register int i=2;i<LIM;i++) {
        if(!vis[i]) p[++p[0]]=i;
        for(register int j=1;j<=p[0]&&i*p[j]<LIM;j++) {
            vis[i*p[j]]=true;
            if(i%p[j]==0) break;
        }
    }
}
inline int64 montgomery(int64 a,int64 k,const int64 &mod) {
	int64 ret=1;
	for(;k;k>>=1) {
		if(k&1) ret=(int128)ret*a%mod;
		a=(int128)a*a%mod;
	}
	return ret;
}
inline bool miller_rabin(const int64 &x) {
    for(register int i=0;i<5;i++) {
        const int64 a=(int64)rand()*rand()%(x-2)+2;
        if(montgomery(a,x-1,x)!=1) return false;
    }
    return true;
}
char ans[1000];
int main() {
	sieve();
	srand(time(NULL));
	const int m=getint();
	for(register int i=1;i<=m;i++) {
		a[i]=getint();
		for(register int j=1;j<=p[0]&&a[i]!=1;j++) {
			while(a[i]%p[j]==0) {
				a[i]/=p[j];
				cnt[p[j]]++;
			}
		}
		if(a[i]==1) continue;
		if(floor(sqrt(a[i]))==ceil(sqrt(a[i]))) {
			cnt[sqrt(a[i])]+=2;
			b[i]=1;
			continue;
		}
		if(miller_rabin(a[i])) {
			cnt[a[i]]++;
			b[i]=2;
			continue;
		}
	}
	for(register int i=1;i<=m;i++) {
		if(a[i]==1||b[i]) continue;
		for(register int j=1;j<=m;j++) {
			if(a[i]==a[j]||a[j]==1) continue;
			const int64 d=std::__gcd(a[i],a[j]);
			if(d==1) continue;
			cnt[d]++;
			cnt[a[i]/d]++;
			goto Next;
		}
		cnt2[a[i]]++;
		Next:;
	}
	int ans1=0,ans2=0;
	for(register std::map<int64,int>::iterator i=cnt.begin();i!=cnt.end();i++) {
		ans1=std::max(ans1,i->second);
	}
	for(register std::map<int64,int>::iterator i=cnt2.begin();i!=cnt2.end();i++) {
		ans1=std::max(ans1,i->second);
	}
	for(register std::map<int64,int>::iterator i=cnt.begin();i!=cnt.end();i++) {
		if(i->second==ans1) ans2++;
	}
	for(register std::map<int64,int>::iterator i=cnt2.begin();i!=cnt2.end();i++) {
		if(i->second==ans1) ans2+=2;
	}
	printf("%d\n",ans1);
	sprintf(ans,"%.Lf",ldexpl(1,ans2));
	ans[strlen(ans)-1]--;
	puts(ans);
	return 0;
}