Editorial for Chữ P


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của happyboy99x

#include <algorithm>
#include <iostream>
#include <cassert>
#include <vector>
#include <cstdio>
using namespace std;

const int MAX = 10000;
vector<int> exponent[MAX + 1];

int main() {
#ifndef ONLINE_JUDGE
    assert(freopen("p.inp", "r", stdin));
    assert(freopen("p.out", "w", stdout));
#endif
    ios::sync_with_stdio(false);
    int n; cin >> n;
    for (int i = 0; i < n; ++i) {
        int x; cin >> x;
        for (int p = 2; p * p <= x; ++p)
            if (x % p == 0) {
                int cnt = 0;
                while (x % p == 0) {
                    x /= p;
                    ++cnt;
                }
                exponent[p].push_back(cnt);
            }
        if (x > 1) exponent[x].push_back(1);
    }
    long long minStep = 0;
    unsigned long long bestPos = 1;
    for (int p = 2; p <= MAX; ++p) if (!exponent[p].empty()) {
        sort(exponent[p].begin(), exponent[p].end());
        int median;
        if ((n - 1) / 2 - (n - (int) exponent[p].size()) < 0) {
            median = 0;
        } else {
            median = exponent[p][(n - 1) / 2 - (n - exponent[p].size())];
        }
        for (int i = 0; i < median; ++i) {
            bestPos *= p;
        }
        for (int i = 0; i < (int) exponent[p].size(); ++i) {
            minStep += abs(median - exponent[p][i]);
        }
        minStep += median * (n - exponent[p].size());
    }
    cout << minStep << ' ' << bestPos << '\n';
    return 0;
}

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), a.end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 100005;
const int X = 10005;
using namespace std;

int notPrime[X], cnt[X], a[N], cntZero[X];
VI f[X], prime;
int n;

void sieve() {
    FOR(i, 2, X) if (notPrime[i] == 0)
    for(int j = i * i; j < X; j += i)
        notPrime[j] = i;
    FOR(i, 2, X) if (notPrime[i] == 0) {
        notPrime[i] = i;
        prime.PB(i);
    }
}

int POW(int a, int p) {
    if (p == 0) return 1;
    int x = POW(a, p >> 1);
    x *= x;
    if (p & 1) return x * a;
    return x;
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    sieve();
    cin >> n;
    int x;
    FOR(i, 0, n) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    LL ans = 1, dist = 0;
    FOR(i, 0, SZ(prime)) {
        FOR(j, 1, X) if (cnt[j]) {
            if (j % prime[i] != 0) cntZero[i] += cnt[j];
            else {
                int jj = j, c = 0;
                while (jj % prime[i] == 0) {
                    c++;
                    jj /= prime[i];
                }
                FOR(step, 0, cnt[j]) f[i].PB(c);
            }
        }
        //cout << prime[i] << ' ' << cntZero[i] << ' ';
        //FOR(j, 0, SZ(f[i])) cout << f[i][j] << ' '; cout << endl;
        sort(ALL(f[i]));
        int pos = (SZ(f[i]) + cntZero[i] - 1) >> 1, med;
        if (pos < cntZero[i]) med = 0; else med = f[i][pos - cntZero[i]];
        if (med == 0) {
            FOR(j, 0, SZ(f[i]))
                dist += f[i][j];
        }
        else {
            ans *= POW(prime[i], med);
            dist += cntZero[i] * med;
            FOR(j, 0, SZ(f[i]))
                dist += abs(f[i][j] - med);
        }
    }
    cout << dist << ' ' << ans;
    return 0;
}

Code mẫu của skyvn97

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<map>
#include<vector>
#define MAX   100100
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define fi   first
#define se   second
using namespace std;
typedef long long ll;
int primeDiv[MAX];
int a[MAX];
int n;
map<int,vector<int> > cntPrime;
int Abs(int x) {
    return (x<0?-x:x);
}
void eratosthene(void) {
    REP(i,2) primeDiv[i]=-1;
    FOR(i,2,MAX-1) if (primeDiv[i]==0)
        for (int j=i;j<MAX;j=j+i) primeDiv[j]=i;
}
void init(void) {
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",&a[i]);
}
void getFactor(int x) {
    while (x>1) {
        int p=primeDiv[x];
        int t=0;
        while (x%p==0) {
            t++;
            x/=p;
        }
        cntPrime[p].push_back(t);
    }
}
pair<int,int> median(vector<int> &v) {
    int pos=(n+1)/2;
    int numZero=n-v.size();
    if (numZero>=pos) {
        int sum=0;
        REP(i,v.size()) sum+=v[i];
        return (make_pair(0,sum));
    }
    REP(zz,numZero) v.push_back(0);
    sort(v.begin(),v.end());
    int sum=0;
    int res=v[pos-1];
    REP(i,v.size()) sum+=Abs(v[i]-res);
    return (make_pair(res,sum));
}
ll pw(int x,int k) {
    ll res=1;
    ll mul=x;
    while (k>0) {
        if (k&1) res*=mul;
        mul*=mul;
        k>>=1;
    }
    return (res);
}
void process(void) {
    int res=0;
    ll best=1;
    FOR(i,1,n) getFactor(a[i]);
    for (map<int,vector<int> >::iterator it=cntPrime.begin();it!=cntPrime.end();it++) {
        pair<int,int> tmp=median(it->se);
        res+=tmp.se;
        best*=pw(it->fi,tmp.fi);
    }
    cout<<res<<" "<<best<<endl;
}
int main(void) {
    //freopen("P.INP","r",stdin);
    //freopen("P.OUT","w",stdout);
    eratosthene();
    init();
    process();
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.