cosenza987

Untitled

Sep 27th, 2021
1,031
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Problem: H. Coprime Ribs
  2. // Contest: Codeforces - UTPC Contest 03-05-21 Div. 2 (Beginner)
  3. // Memory Limit: 256 MB
  4. // Time Limit: 1000 ms
  5. // Date / Time: 2021-09-27 13:49:56
  6. // Author: cosenza
  7. // всё что ни делается - всё к лучшему
  8. // check list -> long long, special cases, array size, mod (a*b%p*c%p not a*b*c%p  ,  (a-b+p)%p not a-b )
  9. //
  10. // Powered by CP Editor (https://cpeditor.org)
  11.  
  12. //#pragma GCC optimize("Ofast")
  13. //#pragma GCC optimize ("unroll-loops")
  14. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  15. //THESE ARE LAST DITCH EFFORTS!!!
  16.  
  17. #include <bits/stdc++.h>
  18.  
  19. using namespace std;
  20.  
  21. const int maxn = 1e6 + 7;
  22.  
  23. long long comp[maxn];
  24. vector<long long> primes;
  25.  
  26. int main() {
  27.     ios_base::sync_with_stdio(false);
  28.     cin.tie(0);
  29.     int n;
  30.     cin >> n;
  31.     for(long long i=2ll;i<maxn;i++){
  32.         if(comp[i]) continue;
  33.         for(long long j=i*i;j<maxn;j+=i) comp[j]=1;
  34.     }
  35.    
  36.     for(long long i=2ll;i<maxn;i++){
  37.         if(!comp[i]) primes.push_back(i);
  38.     }
  39.     vector<int> v(n);
  40.     for(int i = 0; i < n; i++) {
  41.         cin >> v[i];
  42.     }
  43.     vector<set<int>> pfs(n);
  44.     for(int i = 0; i < n; i++) {
  45.         int k = v[i];
  46.         while(k % 2 == 0) {
  47.             k /= 2;
  48.             pfs[i].insert(2);
  49.         }
  50.         for(int j = 3, kk = 2; j * j <= k; j = primes[kk], kk++) {
  51.             while(k % j == 0) {
  52.                 k /= j;
  53.                 pfs[i].insert(j);
  54.             }
  55.         }
  56.         if(k > 2) {
  57.             pfs[i].insert(k);
  58.         }
  59.     }
  60.     map<int, int> cnt, sgn;
  61.     for(int i = 0; i < n; i++) {
  62.         int q = 1;
  63.         for(auto k : pfs[i]) {
  64.             q *= k;
  65.         }
  66.         cnt[q]++;
  67.         sgn[q] = pfs[i].size();
  68.     }
  69.     int ansi = 0;
  70.     for(auto itr : sgn) {
  71.         int x = itr.second, y = cnt[itr.first];
  72.         int tor = y * (y - 1);
  73.         if(x % 2 == 0) {
  74.             ansi -= tor;
  75.         } else {
  76.             ansi += tor;
  77.         }
  78.     }
  79.     cout << ((n * (n - 1)) / 2) - ansi << "\n";
  80.     return 0;
  81. }
RAW Paste Data