Codeforces 1033D Divisors

题目链接http://codeforces.com/contest/1033/problem/D

题意:给n个数,求所有数乘积以后的大数的约数个数,保证每个数约数个数在[3,5]之间。

思路:暴力Pollard Rho被卡到无法自理...然后想着考虑性质已经来不及了...由题目限制条件很容易知道只有4种情况,pq,q^2,q^3,q^4,后三种直接开根判断即可, 关键是前面的,我们考虑两两枚举数对,如果它们gcd大于1,就直接把所有数含有这个gcd的全部算进去,否则说明这个数与其他所有不等于它的数互质,也即这个数分解出来的两个质数是独立的,我们不需要求出是什么,直接算出贡献即可。

#include <bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1e5+10;
const int P=998244353;
int n,i,j,ans=1;
ll a[N];
map<ll,int>mp;
inline ll test(ll a,int b){
    ll ret=pow(a,1./b)+.5;
    ll tmp=1;
    for (int i=1;i<=b;++i) tmp*=ret;
    if (tmp==a) return ret;
    return -1;
}
inline void up(ll x){
    if (mp.find(x)!=mp.end()) return;
    for (int i=1;i<=n;++i){
        ll u=a[i];
        while (!(u%x)) ++mp[x],u/=x;
    }
}
int main(){
    read(n);
    for (i=1;i<=n;++i) read(a[i]);
    for (i=1;i<=n;++i){
        ll tmp=-1;
        for (j=4;j>=2;--j){
            if (~(tmp=test(a[i],j))){
                up(tmp);
                break;
            }
        }
        if (!~tmp){
            bool f=0;
            for (j=1;j<=n;++j)if(a[j]!=a[i] && __gcd(a[i],a[j])>1){
                ll u=__gcd(a[i],a[j]);
                ll v=a[i]/u;
                up(u),up(v);
                f=1;
                break;
            }
            if (!f){
                for (j=1;j<i;++j)if(a[j]==a[i])f=1;
                if (!f){
                    int cnt=0;
                    for (j=1;j<=n;++j)if(a[j]==a[i])cnt++;
                    ans=(ll)ans*(cnt+1)%P;
                    ans=(ll)ans*(cnt+1)%P;
                }
            }
        }
    }
    for (map<ll,int>::iterator it=mp.begin();it!=mp.end();++it){
        int num=(*it).second;
        ans=(ll)ans*(num+1)%P;
    }
    printf("%d\n",ans);
    return 0;
}

唐老师通过了的Pollard Rho板子

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxp = 1e6 + 1, maxv = 25, maxc = (int)2e3 + 1;
int ptot, pr[maxp], d[maxp], cnt;
LL n, p[maxc];
LL mod_add(LL x, LL y, LL p) {
    return (x += y) < p ? x : x - p;
}
LL mod_mul(LL x, LL y, LL p) {
    LL ret = x * y - (LL)((long double)x * y / p + 0.5) * p;
    return ret < 0 ? ret + p : ret;
}
LL mod_pow(LL x, LL k, LL p) {
    LL ret = 1 % p;
    for( ; k > 0; k >>= 1, x = mod_mul(x, x, p))
        (k & 1) && (ret = mod_mul(ret, x, p));
    return ret;
}
bool miller_rabin(LL n) {
    if(n == 2) return 1;
    if(n < 2 || !(n & 1))
        return 0;
    LL s = 0, r = n - 1;
    for( ; !(r & 1); r >>= 1, ++s);
    for(int i = 0; pr[i] < n && pr[i] < maxv; ++i) {
        LL cur = mod_pow(pr[i], r, n), nxt;
        for(int j = 0; j < s; ++j) {
            nxt = mod_mul(cur, cur, n);
            if(nxt == 1 && cur != 1 && cur != n - 1) return 0;
            cur = nxt;
        }
        if(cur != 1) return 0;
    }
    return 1;
}
LL gcd(LL a, LL b) {
    int ret = 0;
    while(a) {
        for( ; !(a & 1) && !(b & 1); ++ret, a >>= 1, b >>= 1);
        for( ; !(a & 1); a >>= 1);
        for( ; !(b & 1); b >>= 1);
        if(a < b)
            swap(a, b);
        a -= b;
    }
    return b << ret;
}
LL pollard_rho(LL n) {
    static LL seq[maxp];
    while(1) {
        LL x = rand() % n, y = x, c = rand() % n;
        LL *px = seq, *py = seq, tim = 0, prd = 1;
        while(1) {
            *py++ = y = mod_add(mod_mul(y, y, n), c, n);
            *py++ = y = mod_add(mod_mul(y, y, n), c, n);
            if((x = *px++) == y) break;
            LL tmp = prd;
            prd = mod_mul(prd, abs(y - x), n);
            if(!prd) return gcd(tmp, n);
            if((++tim) == maxv) {
                if((prd = gcd(prd, n)) > 1 && prd < n) return prd;
                tim = 0;
            }
        }
        if(tim && (prd = gcd(prd, n)) > 1 && prd < n) return prd;
    }
}
void decompose(LL n) {
    for(int i = 0; i < cnt; ++i)
        if(n % p[i] == 0) {
            p[cnt++] = p[i];
            n /= p[i];
        }
    if(n < maxp) {
        for( ; n > 1; p[cnt++] = d[n], n /= d[n]);
    } else if(miller_rabin(n)) {
        p[cnt++] = n;
    } else {
        LL fact = pollard_rho(n);
        decompose(fact), decompose(n / fact);
    }
} // prepare pr(prime) and d(minimal factor)
int main() {
    for(int i = 2; i < maxp; ++i) {
        if(!d[i])
            pr[ptot++] = d[i] = i;
        for(int j = 0, k; (k = i * pr[j]) < maxp; ++j) {
            d[k] = pr[j];
            if(d[i] == pr[j])
                break;
        }
    }
    int m, mod = 998244353;
    scanf("%d", &m);
    while(m--) {
        scanf("%lld", &n);
        decompose(n);
    }
    sort(p, p + cnt);
    int ans = 1;
    for(int i = 0; i < cnt; ) {
        int ctr = 0;
        for(LL pp = p[i]; i < cnt && p[i] == pp; ++i, ++ctr);
        ans = ans * (ctr + 1LL) % mod;
    }
    printf("%d\n", ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注