fork(1) download
copy 
  1. #include "bits/stdc++.h"
  2.  
  3. #define clr(x) memset((x), 0, sizeof(x))
  4. #define all(x) (x).begin(), (x).end()
  5. #define pb push_back
  6. #define mp make_pair
  7. #define in(x) int (x); input((x));
  8. #define x first
  9. #define y second
  10.  
  11. using namespace std;
  12.  
  13. template<typename T>
  14. T gcd(T x, T y) {
  15.     while (y > 0) {
  16.         x %= y;
  17.         swap(x, y);
  18.     }
  19.     return x;
  20. }
  21.  
  22. template<class _T>
  23. inline _T sqr(const _T &x) {
  24.     return x * x;
  25. }
  26.  
  27. template<class _T>
  28. inline string tostr(const _T &a) {
  29.     ostringstream os("");
  30.     os << a;
  31.     return os.str();
  32. }
  33.  
  34. typedef long double ld;
  35. typedef long long ll;
  36. typedef unsigned long long ull;
  37. typedef pair<int, int> PII;
  38. typedef pair<long long, long long> PLL;
  39. const long double PI = 3.1415926535897932384626433832795L;
  40.  
  41. template<typename T>
  42. inline void input(T &a) {
  43.     static int c;
  44.     a = 0;
  45.     while (!isdigit(c = getchar()) && c != '-') {}
  46.     char neg = 0;
  47.     if (c == '-') {
  48.         neg = 1;
  49.         c = getchar();
  50.     }
  51.     while (isdigit(c)) {
  52.         a = 10 * a + c - '0';
  53.         c = getchar();
  54.     }
  55.     if (neg) a = -a;
  56. }
  57.  
  58. template<typename T = int>
  59. inline T nxt() {
  60.     T res;
  61.     input(res);
  62.     return res;
  63. }
  64.  
  65.  
  66. int primes[] = {2, 3, 5, 7, 11, 13, 17, 19};
  67.  
  68. long long VMAX = 1000000;
  69.  
  70. int best = 0;
  71.  
  72. void rec(int pos, int cnt, int prev, long long cur) {
  73.     if (pos == 8) {
  74.         best = max(best, cnt);
  75.         return;
  76.     }
  77.     for (int i = 0; i <= 100 && cur <= VMAX; ++i) {
  78.         rec(pos + 1, cnt * (2 * i + 1), i, cur);
  79.         cur *= primes[pos];
  80.     }
  81. }
  82. const int N = 1000000;
  83. int lp[N + 1];
  84. int dp[N + 1];
  85.  
  86. int pr[20];
  87. int deg[20];
  88. int sz;
  89. long long cur;
  90. long long cur2;
  91. int l[N + 1], r[N + 1];
  92.  
  93. int ans;
  94.  
  95. inline void rec(int pos, long long cur1) {
  96.     if (pos == sz) {
  97.         if (cur2 > N * cur1) return;
  98.         long long v = cur2 / cur1;
  99.         ans += l[cur1] && (r[v] - l[v]);
  100.         return;
  101.     }
  102.     for (int i = 0; i <= 2 * deg[pos] && cur1 < cur; ++i) {
  103.         rec(pos + 1, cur1);
  104.         cur1 *= pr[pos];
  105.     }
  106. }
  107.  
  108. int main(int argc, char **argv) {
  109. #ifdef LOCAL
  110.     freopen("input.txt", "r", stdin);
  111.     //freopen("output.txt", "w", stdout);
  112. #endif
  113.  
  114.     for (int i = 2; i <= N; ++i) {
  115.         if (!lp[i]) {
  116.             for (int j = i, k = 1; j <= N; j += i, ++k) {
  117.                 if (!lp[j]) {
  118.                     lp[j] = i;
  119.                     dp[j] = k;
  120.                 }
  121.             }
  122.         }
  123.     }
  124.     int n = nxt();
  125.     int a[n];
  126.     for (int i = 0; i < n; ++i) {
  127.         a[i] = nxt();
  128.         r[a[i]]++;
  129.     }
  130.  
  131.     for (int i = 0; i < n; ++i) {
  132.         int d = a[i];
  133.         sz = 0;
  134.         while (d > 1) {
  135.             int p = lp[d];
  136.             pr[sz] = p;
  137.             deg[sz] = 0;
  138.             while (lp[d] == p) {
  139.                 d = dp[d];
  140.                 ++deg[sz];
  141.             }
  142.             ++sz;
  143.         }
  144.         cur2 = cur = a[i];
  145.         cur2 *= cur2;
  146.         rec(0, 1);
  147.         ++l[a[i]];
  148.     }
  149.  
  150.     cout << ans << "\n";
  151.  
  152. #ifdef LOCAL
  153.     cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC * 1000 << " ms." << endl;
  154. #endif
  155.     return 0;
  156. }
  157.  
Time limit exceeded #stdin #stdout 5s 18728KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YugzJa
language:
C++14 (gcc 8.3)
created:
9 years 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!