fork download
copy 
  1. /*
  2.  * Language: Standard C++23 [-std=c++23]
  3.  * Author: Zang Vũ aka zvwgvx
  4.  * Github & Discord & Facebook: @zvwgvx
  5.  */
  6.  
  7. #pragma GCC optimize("fast-math,O3")
  8. #pragma GCC optimize("no-stack-protector") 
  9. #pragma GCC optimize("unroll-loops")
  10. // #pragma GCC optimize("Ofast")
  11. // #pragma GCC target("tune=native")
  12. // #pragma GCC target("avx,avx2,fma")
  13.  
  14. #include <bits/stdc++.h>
  15.  
  16. using namespace std;
  17.  
  18. #define ENV defined(LOCAL)
  19. #define el cout << '\n'
  20. #define rt return
  21. #define ll long long
  22. #define ull unsigned ll
  23. #define pii pair <int, int>
  24. #define pll pair <ll, ll>
  25. #define vi vector <int>
  26. #define vl vector <ll>
  27. #define vc vector <char>
  28. #define vvi vector <vector <int>>
  29. #define vvl vector <vector <ll>>
  30. #define mts multiset
  31. #define mtm multimap
  32. #define ump unordered_map
  33. #define ust unordered_set
  34. #define umts unordered_multiset
  35. #define umtm unordered_multimap
  36. #define priq priority_queue
  37.  
  38. template <typename T>
  39. T fgcd(T a, T b) {
  40.     if (!a || !b) rt a | b;
  41.     unsigned shift = __builtin_ctzll(a | b);
  42.     a >>= __builtin_ctzll(a);
  43.     while (b) {
  44.         b >>= __builtin_ctzll(b);
  45.         if (a > b) swap(a, b);
  46.         b -= a;
  47.     }
  48.     rt a << shift;
  49. }
  50.  
  51. template <typename T>
  52. T fpow(T base, T exp, T mod) {
  53.     T res = 1;
  54.     for (; exp; exp >>= 1, base = base * base % mod)
  55.         if (exp & 1) res = res * base % mod;
  56.     rt res;
  57. }
  58.  
  59. template <typename T> T lcm(T a, T b) { rt a * (b / fgcd(a, b)); }
  60. template <typename T> void maximize(T& a, T b) { if (a < b) a = b; }
  61. template <typename T> void minimize(T& a, T b) { if (a > b) a = b; }
  62. template <typename T> double lg(T a, T b) { rt log(b) / log(a); }
  63. template <typename T> ull P(T n, T k) { ull res = 1; for (int i = 0; i < k; i++) res *= (n - i); rt res; }
  64. template <typename T> ull C(T n, T k) { ull res = 1; for (int i = 1; i <= k; i++) res = res * (n - i + 1) / i; rt res; }
  65.  
  66. const int MOD = 1e9 + 7;
  67. const int INF = 1e9;
  68. const int LIMIT = 1e6 + 5;
  69.  
  70. #if ENV
  71. void open(const string& file) {
  72.     freopen((file + ".inp").c_str(), "r", stdin);
  73.     freopen((file + ".out").c_str(), "w", stdout);
  74. }
  75. auto start = clock();
  76. void time() { cout << "\n\n[rt] " << 1.0 * (clock() - start) / CLOCKS_PER_SEC; }
  77. #endif
  78.  
  79. vi sieve(int n) {
  80.     vi mu(n+1, 1);
  81.     vi primes;
  82.     bitset<LIMIT> cpst;
  83.     for (int i = 2; i <= n; i++){
  84.         if (!cpst[i]) {
  85.             primes.push_back(i);
  86.             mu[i] = -1;
  87.         }
  88.         for (int p : primes) {
  89.             if ((ll)i * p > n) break;
  90.             cpst[i * p] = true;
  91.             if (i % p == 0) {
  92.                 mu[i * p] = 0;
  93.                 break;
  94.             } else {
  95.                 mu[i * p] = -mu[i];
  96.             }
  97.         }
  98.     }
  99.     rt mu;
  100. }
  101.  
  102. signed main() { 
  103.     cin.tie(nullptr), cout.tie(nullptr)
  104.     -> ios_base::sync_with_stdio(false);
  105.  
  106.     #if ENV 
  107.         open("main");
  108.         srand(time(nullptr));
  109.     #endif
  110.  
  111.     ll n, k;
  112.     cin >> n >> k;
  113.     vl arr(n);
  114.     for (ll &x : arr) cin >> x;
  115.  
  116.     vl b;
  117.     ll max_b = 0;
  118.     for (ll x : arr) {
  119.         if(x % k == 0) {
  120.             ll tmp = x / k;
  121.             b.push_back(tmp);
  122.             if(tmp > max_b) max_b = tmp;
  123.         }
  124.     }
  125.  
  126.     if(b.size() < 2){
  127.         cout << -1;
  128.         rt 0;
  129.     }
  130.  
  131.     vi freq(max_b+1, 0);
  132.     for (ll x : b) {
  133.         freq[x]++;
  134.     }
  135.  
  136.     vl cnt(max_b+1, 0);
  137.     for (int d = 1; d <= max_b; d++){
  138.         for (int j = d; j <= max_b; j += d){
  139.             cnt[d] += freq[j];
  140.         }
  141.     }
  142.  
  143.     vi mu = sieve(max_b);
  144.  
  145.     ll res = 0;
  146.     for (int d = 1; d <= max_b; d++){
  147.         ll pairs = cnt[d] * (cnt[d] - 1LL) >> 1; 
  148.         res += mu[d] * pairs;
  149.     }
  150.  
  151.     cout << (res == 0 ? -1 : res);
  152.  
  153.     #if ENV 
  154.         time();
  155.     #endif
  156.  
  157.     rt 0;   
  158. }
  159.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/vg3oXT
language:
C++14 (clang 8.0)
created:
10 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!