fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
  5. #define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
  6.  
  7. using ll = long long;
  8.  
  9. template<typename X, typename Y>
  10. bool chmax(X& a, Y b) { return (a < b) ? a = b, 1 : 0; }
  11. template<typename X, typename Y>
  12. bool chmin(X& a, Y b) { return (a > b) ? a = b, 1 : 0; }
  13.  
  14.  
  15. const int INF = 1e9 + 67;
  16. const int MAXA = 1e6;
  17. const int MAXN = 1e5 + 5;
  18.  
  19. int N, A[MAXN];
  20.  
  21. namespace Subtask1 {
  22.     bool check() {
  23.         return N == 2;
  24.     }
  25.     int cnt[MAXA + 5];
  26.     void solve() {
  27.         int T = A[1];
  28.         FOR(p, 2, (int)sqrt(T)) if (T % p == 0) {
  29.             int e = 0;
  30.             while (T % p == 0) T /= p, e++;
  31.             cnt[p] = e;
  32.         }
  33.         if (T > 1) cnt[T] = 1;
  34.         T = A[2];
  35.         int D = 0;
  36.         FOR(p, 2, MAXA) {
  37.             if (T % p == 0) {
  38.                 int e = 0;
  39.                 while (T % p == 0) T /= p, e++;
  40.                 D += abs(e - cnt[p]);
  41.             } else D += cnt[p];
  42.         }
  43.         cout << D << " " << 2 << "\n";
  44.         cout << D << " " << 1 << "\n";
  45.     }
  46. }
  47.  
  48. int spf[MAXA];
  49.  
  50. void precompute() {
  51.     FOR(i, 1, MAXA) spf[i] = i;
  52.     for (int i = 2; i * i <= MAXA; i++) if (spf[i] == i)
  53.         for (int j = i * i; j <= MAXA; j += i) if (spf[j] == j) 
  54.             spf[j] = i;
  55. }
  56.  
  57. namespace Subtask2 {
  58.     bool check() {
  59.         return N <= 1000;
  60.     }
  61.     int F[MAXA + 5];
  62.     int f(int x, int y) { return F[x] + F[y] - 2 * F[__gcd(x, y)]; }
  63.     void solve() {
  64.         precompute();
  65.         FOR(i, 2, MAXA) F[i] = F[i / spf[i]] + 1;
  66.         vector<pair<int, int>> ans(N + 5, make_pair(INF, -1));
  67.         FOR(i, 1, N) FOR(j, i + 1, N) {
  68.             int D = f(A[i], A[j]);
  69.             chmin(ans[i], make_pair(D, j));
  70.             chmin(ans[j], make_pair(D, i));
  71.         }
  72.         FOR(i, 1, N) cout << ans[i].first << " " << ans[i].second << "\n";
  73.     }
  74. }
  75.  
  76. namespace Fulltask {
  77.     vector<int> primes;
  78.     pair<int, int> best[MAXA + 5], _best[MAXA + 5];
  79.     inline bool update(int u, int d, int id) {
  80.         if (id == -1) return false;
  81.         pair<int, int> X = make_pair(d, id);
  82.         if (id == best[u].second) return chmin(best[u], X);
  83.         if (id == _best[u].second) return chmin(_best[u], X);
  84.         if (X < best[u]) {
  85.             _best[u] = best[u];
  86.             best[u] = X;
  87.             return true;
  88.         }
  89.         return chmin(_best[u], X);
  90.     }
  91.     inline void merge(int v, int u) {
  92.         if (best[u].second != -1) update(v, best[u].first + 1, best[u].second);
  93.         if (_best[u].second != -1) update(v, _best[u].first + 1, _best[u].second);
  94.     }
  95.     void solve() {
  96.         precompute();
  97.         FOR(i, 2, MAXA) if (spf[i] == i) 
  98.             primes.push_back(i);
  99.         FOR(i, 1, MAXA) best[i] = _best[i] = make_pair(INF, -1);
  100.         FOR(i, 1, N) update(A[i], 0, i);
  101.         FORD(u, MAXA, 2) if (best[u].second != -1) {    
  102.             int T = u;
  103.             while (T > 1) {
  104.                 int p = spf[T];
  105.                 merge(u / p, u);
  106.                 while (T % p == 0) T /= p;
  107.             }
  108.         }
  109.         FOR(u, 1, MAXA) if (best[u].second != -1) {
  110.             for (int p : primes) {
  111.                 if (1LL * u * p > MAXA) break;
  112.                 merge(u * p, u);
  113.             }
  114.         }
  115.         FOR(i, 1, N) {
  116.             pair<int, int> ans = make_pair(INF, -1);
  117.             if (best[A[i]].second != -1 && best[A[i]].second != i) chmin(ans, best[A[i]]);
  118.             if (_best[A[i]].second != -1 && _best[A[i]].second != i) chmin(ans, _best[A[i]]);
  119.             cout << ans.first << " " << ans.second << "\n";
  120.         }
  121.     }
  122. }
  123.  
  124. void solve() {
  125.     cin >> N;
  126.     FOR(i, 1, N) cin >> A[i];
  127.     if (Subtask1::check()) Subtask1::solve();
  128.     else if (Subtask2::check()) Subtask2::solve();
  129.     else Fulltask::solve();
  130. }
  131.  
  132. int main() {
  133.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  134.  
  135.     // freopen("ENERGY.INP", "r", stdin);
  136.     // freopen("ENERGY.OUT", "w", stdout);
  137.  
  138.     int tests = 1; // cin >> tests;
  139.     while (tests--) solve();
  140.  
  141.     #ifdef LOCAL
  142.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  143.     #endif
  144.     return 0;
  145. }
Success #stdin #stdout 0.01s 13836KB
comments (?)
stdin
copy 
3
6 5 25
stdout
copy 
3 2
1 3
1 2
https://ideone.com/ExT7fo
Chọn ĐTQG An Giang 2026 - Năng lượng
language:
C++14 (gcc 8.3)
created:
17 hours 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!