[HOJ 162][POI 17 Stage 1]找因數

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

先備知識: 質數判定法
假設這n個數的乘積是N好了
總之，先用輾轉相除法把這n個數分解成更多個兩兩互質的數，但是乘積還是等於N，這個分解完的數列就壓縮存在S裡面，請注意，這個互質的性質很重要
然後就是對S裡面的每個數做質因數分解算次方數，最後就可以直接找k了
由於數字很大，有時不能直接對他做質因數分解
首先可以設想一個很大很大的數字M，用10^6以內的質數試除完畢，剩下一個數，叫它A好了
先用上網查的(XD)質數判定法判斷A是不是質數，如果是，就結束了
因為次數是很重要的資訊，所以先開根號看看是不是某個質數平方，如果是，就結束了
如果上述方法都失敗，就代表A一定是兩個>10^6的相異質數P和Q相乘，這時候其實不用找出P和Q是甚麼，可以直接用A和A+1來代表這兩個質數
為甚麼呢?
上面有提到，經過處理，S裡面每兩個數都會互質，因此不會有另外一個數的因數也包含P、Q或A
又因為A一定是大於10^6的奇數(不然就會在前面的試除過程被解決掉了)，所以A和A+1這兩個key一定不會被其他人用到
既然這麼好康，當然不客氣就把A和A+1當作P和Q了XD
現在，我們成功把這個很大很大的數質因數分解了！(其實只知道次方啦，不過這樣就夠了XD)
接下來的步驟就很明朗了
找出最大的k和次方數等於k的質數個數
至於「第二行請輸出 k 最大時 d 有多少種可能」，仔細想想就會發現可以套用一下計算因數個數的技巧，它其實就是「2^(符合條件的質數個數)-1」
要注意的是這中間涉及很多溢位問題，要設計一個方法支持(long long)*(long long)%(long long)這個運算
我原本直接貼大數模板結果TLE了QQ
不過後來的方式時間效率還不錯啦XD
耶！

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=9223372036854775807LL;
LL Mul(LL _a,LL _b,const LL mod)
{
    vector<LL>a,b;
    while(_a)a.push_back(_a%10LL),_a/=10LL;
    while(_b)b.push_back(_b%10LL),_b/=10LL;
    vector<LL>c;c.resize((int)a.size()+(int)b.size()-1,0LL);
    for(int i=0;i<(int)a.size();i++)for(int j=0;j<(int)b.size();j++)c[i+j]+=a[i]*b[j];
    LL now=0LL;
    for(int i=(int)c.size()-1;i>=0;i--)
    {
        LL tmp=now;
        for(int j=1;j<10;j++)
        {
            while(tmp>INF-now)tmp-=mod;
            (tmp+=now)%=mod;
        }
        while(tmp>INF-c[i])tmp-=mod;
        (tmp+=c[i])%=mod;
        now=tmp;
    }
    return now;
}
LL Pow(LL a,LL p,const LL mod)
{
    LL ans=1LL;
    while(p)
    {
        if(p&1)ans=Mul(ans,a,mod);
        a=Mul(a,a,mod);
        p>>=1; 
    }
    return ans;
}
bool IsPrime(LL n)
{
    if(n==2LL)return true;
    if(n<2LL||n%2LL==0LL)return false;
    LL u=n-1LL;
    int t=0;
    while(u%2LL==0LL){u>>=1,t++;}
    static LL sprp[7]={2,325,9375,28178,450775,9780504,1795265022};
    for(int i=0;i<7;i++)
    {
        LL a=sprp[i]%n;
        if(a==0LL||a==1LL||a==n-1LL)continue;
        LL x=Pow(a,u,n);
        if(x==1LL||x==n-1LL)continue;
        for(int j=0;j<t-1;j++)
        {
            x=Mul(x,x,n);
            if(x==1LL)return false;
            if(x==n-1LL)break;
        }
        if(x==n-1LL)continue;
        return false;
    }
    return true;
}
void Add(map<LL,int>&s,const LL v,const int cnt)
{
    auto it=s.find(v);
    if(it==s.end())s[v]=cnt;
    else if(!(it->second+=cnt))s.erase(it);
}
LL Gcd(const LL a,const LL b){return b==0LL?a:Gcd(b,a%b);}
int N;
map<LL,int>S;
void Initialize()
{
    map<LL,int>tmp;
    for(int i=0;i<N;i++)
    {
        static LL v;
        scanf("%lld",&v);
        Add(tmp,v,1);
    }
    S.clear();
    while(!tmp.empty())
    {
        auto it=tmp.begin();
        const auto begin=it++;
        for(;;it++)
        {
            if(it==tmp.end())
            {
                Add(S,begin->first,begin->second);
                tmp.erase(begin);
                break;
            }
            const LL g=Gcd(begin->first,it->first);
            if(g!=1LL)
            {
                const int cnt1=begin->second,cnt2=it->second;
                const LL v1=begin->first,v2=it->first;
                Add(tmp,v1/g,cnt1),Add(tmp,v2/g,cnt2),Add(tmp,g,cnt1+cnt2);
                Add(tmp,v1,-cnt1),Add(tmp,v2,-cnt2);
                break;
            }
        }
    }
    map<LL,int>().swap(tmp);
}
vector<LL>P;
void Factorize(LL n,map<LL,int>&f)
{
    f.clear();
    for(int i=0;i<(int)P.size()&&P[i]*P[i]<=n;i++)
    {
        int cnt=0;
        while(n%P[i]==0LL)n/=P[i],cnt++;
        if(cnt)Add(f,P[i],cnt);
    }
    if(n==1LL)return;
    LL v=sqrt(n);
    assert(v*v<=n&&(v+1LL)*(v+1LL)>n);
    if(v*v==n)Add(f,v,2);
    else
    {
        Add(f,n,1);
        if(!IsPrime(n))Add(f,n+1LL,1);
    }
}
map<LL,int>F;
void Solve()
{
    F.clear();
    for(const auto it:S)
    {
        static map<LL,int>tmp;tmp.clear();
        Factorize(it.first,tmp);
        for(const auto elem:tmp)
        {
            assert(F.find(elem.first)==F.end());
            F[elem.first]=it.second*elem.second;
        }
    }
}
main()
{
//    freopen("in.txt","r",stdin);
    if(true)
    {
        bool *notp=new bool[1000001];
        for(int i=0;i<=1000000;i++)notp[i]=false;
        P.clear();
        for(int i=2;i<=1000000;i++)if(!notp[i])
        {
            P.push_back(i);
            for(int j=2;i*j<=1000000;j++)notp[i*j]=true;
        }
        delete[]notp;
    }
//    for(int i=0;i<100;i++)if(IsPrime(i))printf("%d\n",i);
    while(scanf("%d",&N)==1)
    {
        Initialize();
        Solve();
        map<int,vector<LL> >ans;
        for(const auto it:F)ans[it.second].push_back(it.first);
        auto it=ans.end();it--;
        printf("%d\n",it->first);
        vector<int>big;big.push_back(1);
        for(int cnt=(it->second).size();cnt--;)
        {
            for(int &v:big)v*=2;
            for(int i=0;i<(int)big.size();i++)if(big[i]>=10)
            {
                if(i+1==(int)big.size())big.push_back(0);
                big[i+1]+=big[i]/10;
                big[i]%=10;
            }
        }
        assert(big[0]>1&&big[0]<10),big[0]--;
        for(int i=(int)big.size()-1;i>=0;i--)assert(big[i]>=0&&big[i]<10),putchar('0'+big[i]);puts("");
        break;
    }
    return 0;
}