cjb-poi2010divinedivisor2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;++i)
#define mp make_pair
#define pb push_back
const int S=7;
int n;
int pri[1100000],v[1100000],top=0;
long long a[610];
int dic[1100000];
long long gcd(long long x,long long y)
{
    return y==0?x:gcd(y,x%y);
}

long long mult_mod(long long x,long long y,long long mod){
    x%=mod; y%=mod; 
    if (x<1e9 && y<1e9) return x*y%mod;
    long long k=(long long)((long double)x*y/mod),res;
    res=(x*y-k*mod)%mod;
    return res<0? res+mod:res;
}
long long pow_mod(long long x,long long n,long long mod){//x^n%c
    if(n==1)return x%mod;
    x%=mod; long long tmp=x; long long ret=1;
    while(n){
        if(n&1) ret=mult_mod(ret,tmp,mod);
        tmp=mult_mod(tmp,tmp,mod); n>>=1;
    }
    return ret;
}
bool check(long long a,long long n,long long x,long long t){
    long long ret=pow_mod(a,x,n);long long last=ret;
    for(int i=1;i<=t;i++){
        ret=mult_mod(ret,ret,n);
        if(ret==1&&last!=1&&last!=n-1) return true;//合数
        last=ret;
    }
    if(ret!=1) return true;return false;
}
const int test[7]={2, 325, 9375, 28178, 450775, 9780504, 1795265022};
bool Miller_Rabin(long long n){// Miller_Rabin()算法素数判定
    if(n<2)return false;
    if(n==2)return true;
    if((n&1)==0) return false;//偶数
    long long x=n-1,t=0;
    while((x&1)==0){x>>=1;t++;}
    for(int i=0;i<S;i++){
        long long a=test[i]%(n-1)+1;
        if(check(a,n,x,t))return false;//合数
    }
    return true;
}

struct Int
{
    int a[1000];
    int tot;
    static const int mob=1000000000;
    Int():a(),tot(){a[0]=1;}
    Int& operator <<= (int x)
    {
        while(x--)
        {
            for(int i=0;i<=tot;++i)
            a[i]<<=1;
            for(int i=0;i<=tot;++i)
            if(a[i]>=mob)
            {
                a[i+1]+=a[i]/mob;
                a[i]%=mob;
            }
            if(a[tot+1]) ++tot;
        }
        return *this;
    }
    void print()
    {
        --a[0];
        printf("%d",a[tot]);
        for(int i=tot-1;~i;--i)
        printf("%09d",a[i]);
    }
}tt;

int ans=0,cnt=0;

inline long long getsqrt(long long n){
  long long x=sqrt(n);
  for(long long i=x-2;i<=x+2;i++)if(i*i==n)return i;
  return 0;
}

vector<long long> waittry;
map<long long,int> factor;
void work(long long x)
{
    for(auto p:waittry)if (x%p==0){ factor[x/p]++,factor[p]++; return; }
    for(int i=1;i<=n;i++)
    {
        long long t=gcd(a[i],x);
        if (t==1 || t==x)continue;
        factor[x/t]++;
        factor[t]++;
        return;
    }
    if (x!=1)factor[-x]++;
}
int main()
{
    cin>>n; rep(i,n)scanf("%lld",&a[i]);
    factor.clear(); waittry.clear();
    for(int i=2;i<=1000000;i++)
    {
        if (!v[i])
        {
            pri[++top]=i;
        }

        for(int j=1;j<=top && i*pri[j]<=1000000;j++)
        {
            v[i*pri[j]]=1;
            if (i%pri[j]==0)break;
        }
    }

    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=top && pri[j]<=a[i];j++)while(a[i]%pri[j]==0)factor[pri[j]]++,a[i]/=pri[j];
        if (a[i]==1)continue;
        if (Miller_Rabin(a[i])){ factor[a[i]]++; waittry.pb(a[i]); continue; }
        long long t=getsqrt(a[i]);
        if (t){ factor[t]++; factor[t]++; waittry.pb(t); continue; }
        a[++cnt]=a[i];
    }
    n=cnt;

    for(int i=1;i<=n;i++)work(a[i]);
    for(auto p:factor)
        if (p.second>ans)ans=p.second,cnt=(p.first<0?2:1);
        else if (p.second==ans)cnt+=(p.first<0?2:1);

    cout<<ans<<endl;
    tt<<=cnt;
    tt.print(); puts("");

    return 0;
}
}}}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;++i)
#define mp make_pair
#define pb push_back
const int S=7;
int n;
int pri[1100000],v[1100000],top=0;
long long a[610];
int dic[1100000];
long long gcd(long long x,long long y)
{
    return y==0?x:gcd(y,x%y);
}
long long mult_mod(long long x,long long y,long long mod){
    x%=mod; y%=mod; 
    if (x<1e9 && y<1e9) return x*y%mod;
    long long k=(long long)((long double)x*y/mod),res;
    res=(x*y-k*mod)%mod;
    return res<0? res+mod:res;
}
long long pow_mod(long long x,long long n,long long mod){//x^n%c
    if(n==1)return x%mod;
    x%=mod; long long tmp=x; long long ret=1;
    while(n){
        if(n&1) ret=mult_mod(ret,tmp,mod);
        tmp=mult_mod(tmp,tmp,mod); n>>=1;
    }
    return ret;
}
bool check(long long a,long long n,long long x,long long t){
    long long ret=pow_mod(a,x,n);long long last=ret;
    for(int i=1;i<=t;i++){
        ret=mult_mod(ret,ret,n);
        if(ret==1&&last!=1&&last!=n-1) return true;//合数
        last=ret;
    }
    if(ret!=1) return true;return false;
}
const int test[7]={2, 325, 9375, 28178, 450775, 9780504, 1795265022};
bool Miller_Rabin(long long n){// Miller_Rabin()算法素数判定
    if(n<2)return false;
    if(n==2)return true;
    if((n&1)==0) return false;//偶数
    long long x=n-1,t=0;
    while((x&1)==0){x>>=1;t++;}
    for(int i=0;i<S;i++){
        long long a=test[i]%(n-1)+1;
        if(check(a,n,x,t))return false;//合数
    }
    return true;
}
struct Int
{
    int a[1000];
    int tot;
    static const int mob=1000000000;
    Int():a(),tot(){a[0]=1;}
    Int& operator <<= (int x)
    {
        while(x--)
        {
            for(int i=0;i<=tot;++i)
            a[i]<<=1;
            for(int i=0;i<=tot;++i)
            if(a[i]>=mob)
            {
                a[i+1]+=a[i]/mob;
                a[i]%=mob;
            }
            if(a[tot+1]) ++tot;
        }
        return *this;
    }
    void print()
    {
        --a[0];
        printf("%d",a[tot]);
        for(int i=tot-1;~i;--i)
        printf("%09d",a[i]);
    }
}tt;
int ans=0,cnt=0;
inline long long getsqrt(long long n){
  long long x=sqrt(n);
  for(long long i=x-2;i<=x+2;i++)if(i*i==n)return i;
  return 0;
}
vector<long long> waittry;
map<long long,int> factor;
void work(long long x)
{
    for(auto p:waittry)if (x%p==0){ factor[x/p]++,factor[p]++; return; }
    for(int i=1;i<=n;i++)
    {
        long long t=gcd(a[i],x);
        if (t==1 || t==x)continue;
        factor[x/t]++;
        factor[t]++;
        return;
    }
    if (x!=1)factor[-x]++;
}
int main()
{
    cin>>n; rep(i,n)scanf("%lld",&a[i]);
    factor.clear(); waittry.clear();
    for(int i=2;i<=1000000;i++)
    {
        if (!v[i])
        {
            pri[++top]=i;
        }
        for(int j=1;j<=top && i*pri[j]<=1000000;j++)
        {
            v[i*pri[j]]=1;
            if (i%pri[j]==0)break;
        }
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=top && pri[j]<=a[i];j++)while(a[i]%pri[j]==0)factor[pri[j]]++,a[i]/=pri[j];
        if (a[i]==1)continue;
        if (Miller_Rabin(a[i])){ factor[a[i]]++; waittry.pb(a[i]); continue; }
        long long t=getsqrt(a[i]);
        if (t){ factor[t]++; factor[t]++; waittry.pb(t); continue; }
        a[++cnt]=a[i];
    }
    n=cnt;
    for(int i=1;i<=n;i++)work(a[i]);
    for(auto p:factor)
        if (p.second>ans)ans=p.second,cnt=(p.first<0?2:1);
        else if (p.second==ans)cnt+=(p.first<0?2:1);
    cout<<ans<<endl;
    tt<<=cnt;
    tt.print(); puts("");
    return 0;
}