题解 P3499 【[POI2010]NAJ-Divine Divisor】

skylee · 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种情况：

对于每个质数，我们统计其出现次数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;
}