fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define el '\n'
  4. #define fi first
  5. #define sec second
  6. #define pb push_back
  7. #define ll long long
  8. #define pii pair<int,int>
  9. #define sz(v) (int)(v).size()
  10. #define all(v) (v).begin(),(v).end()
  11. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  12. #define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; i--)
  13.  
  14. using namespace std;
  15.  
  16. const long long LLNF = 0x3f3f3f3f3f3f3f3f;
  17. const int INF = 0x3f3f3f3f;
  18. const int MAX_N = 2e5;
  19. const int MAX_A = 1e6;
  20.  
  21. vector<int> pos[MAX_A + 5]; // Lưu vị trí xuất hiện của từng số
  22. pii best[MAX_A + 5][2]; // Mảng best, best[d][0] là tốt nhất, best[d][1] là tốt nhì
  23. int omega[MAX_A + 5]; // Mảng lưu Ω của từng số
  24. int spf[MAX_A + 5]; // Mảng spf để phân tích ra thừa số nguyên tố rồi sinh ra các ước
  25. int a[MAX_N + 5];
  26. int n;
  27.  
  28. void Input(){
  29.     cin >> n;
  30.     FOR(i, 1, n){
  31.         cin >> a[i];
  32.         pos[a[i]].pb(i); // với mỗi số a[i] thì nó xuất hiện ở những vị trí nào
  33.     }
  34. }
  35.  
  36. void Sieve_SPF(int limit){ // Tạo mảng spf
  37.     FOR(i, 2, limit) if(!spf[i]){
  38.         spf[i] = i;
  39.  
  40.         for(ll j = 1LL * i * i; j <= limit; j += i){
  41.             if(!spf[j]) spf[j] = i;
  42.         }
  43.     }
  44. }
  45.  
  46. void update_best(int d, pii val){ // hàm update cho mảng best
  47.     if(best[d][0] > val){
  48.         best[d][1] = best[d][0];
  49.         best[d][0] = val;
  50.     }
  51.     else if(best[d][1] > val){
  52.         best[d][1] = val;
  53.     }
  54. }
  55.  
  56. void Prepare(){
  57.     Sieve_SPF(MAX_A);
  58.  
  59.     omega[1] = 0;
  60.     FOR(i, 2, MAX_A) omega[i] = omega[i / spf[i]] + 1; //tính Ω cho từng số
  61.  
  62.     FOR(i, 1, MAX_A){
  63.         best[i][0] = best[i][1] = {INF, INF}; // gán trước phòng trước hợp số d không có bội nào tồn tại trong mảng thì kết quả sẽ sau khi dùng công thức sẽ là âm vô cùng -> không ảnh hưởng tới kết quả cuối
  64.  
  65.         for(int j = i; j <= MAX_A; j += i) if(sz(pos[j])){
  66.                 update_best(i, {omega[j], pos[j][0]}); // xem số j có phù hợp để làm số tốt nhất cho best[i] không
  67.                 if(sz(pos[j]) > 1) update_best(i, {omega[j], pos[j][1]});// nếu số j xuất hiện 2 lần trong mảng thì cập nhật thêm lần nữa vị biết đâu cả vị trí nhất và nhì thì đều là j nhưng chỉ khác index thì sao
  68.  
  69.         }
  70.     }
  71. }
  72.  
  73. vector<int> get_divisors(int x){ // hàm sinh ước
  74.     vector<pii> factor;
  75.  
  76.     while(x > 1){
  77.         int p = spf[x], cnt = 0;
  78.         while(x % p == 0){
  79.             x /= p;
  80.             cnt++;
  81.         }
  82.         factor.pb({p, cnt});
  83.     }
  84.  
  85.     vector<int> res = {1};
  86.     for(pii f : factor){
  87.         int p = f.fi, cnt = f.sec;
  88.         int cur = 1, cur_sz = sz(res);
  89.  
  90.         FOR(i, 1, cnt){
  91.             cur *= p;
  92.             for(int j = 0; j < cur_sz; j++) res.pb(res[j] * cur);
  93.         }
  94.     }
  95.  
  96.     return res;
  97. }
  98.  
  99. void update_ans(int &best_idx, int &min_dist, int i, int d, pii good){ //nhìn tự hiểu
  100.     int dist = omega[a[i]] + good.fi - 2 * omega[d];
  101.  
  102.     if(min_dist > dist){
  103.         min_dist = dist;
  104.         best_idx = good.sec;
  105.     }
  106.     else if(min_dist == dist){
  107.         best_idx = min(best_idx, good.sec);
  108.     }
  109. }
  110.  
  111. void Solve(){
  112.     FOR(i, 1, n){
  113.         int best_idx, min_dist = INF;
  114.  
  115.         vector<int> divi = get_divisors(a[i]); // các ước của a[i]
  116.         for(int d : divi){
  117.             if(best[d][0].sec != i) update_ans(best_idx, min_dist, i, d, best[d][0]); // nếu số tốt nhất của d không phải là a[i] thì lấy
  118.             else update_ans(best_idx, min_dist, i, d, best[d][1]); // còn nếu số tốt nhất chính là a[i] thì dùng số tốt nhì
  119.         }
  120.  
  121.         cout << best_idx << " " << min_dist << el; // cout kết quả
  122.     }
  123. }
  124.  
  125. int main(){
  126.     ios_base::sync_with_stdio(0);
  127.     cin.tie(0);
  128.  
  129.     Input();
  130.     Prepare();
  131.     Solve();
  132.  
  133.     return 0;
  134. }
  135.  
Success #stdin #stdout 0.13s 50464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kncuPd
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!