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.
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