fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll int
  4. #define dbg(x) cout << #x << " : " << x << endl
  5. #define rep(i, a, b) for (int i = (a); i <= (b); i++)
  6. #define inf 1000000000000000000
  7. priority_queue<ll, vector<ll>, greater<int>> qp;
  8. priority_queue<ll> qr;
  9. #define N 20000010
  10. #define mod 1000000007
  11. #define cnt_ones __builtin_popcount
  12. bool isPrime[N + 1];
  13. vector<int> primes;
  14. void sieve()
  15. {
  16.     for (int i = 0; i <= N; ++i)
  17.     {
  18.         isPrime[i] = true;
  19.     }
  20.     isPrime[0] = false;
  21.     isPrime[1] = false;
  22.     for (int i = 2; i * i <= N; ++i)
  23.     {
  24.         if (isPrime[i] == true)
  25.         {
  26.             // Mark all the multiples of i as composite numbers
  27.             for (int j = i * i; j <= N; j += i)
  28.                 isPrime[j] = false;
  29.         }
  30.     }
  31. }
  32. bool aka(int source)
  33. {
  34.     int tmp = (int)sqrt(source);
  35.     if (tmp * tmp == source and isPrime[tmp])
  36.         return true;
  37.     return false;
  38. }
  39. int main()
  40. {
  41.     sieve();
  42.     for (int i = 1; i <= N; i++)
  43.         if (isPrime[i])
  44.             primes.push_back(i);
  45.     // cout<<primes.size();
  46.     int res = 0;
  47.     int tc;
  48.     cin >> tc;
  49.     while (tc--)
  50.     {
  51.         int n;
  52.         cin >> n;
  53.         int ans = 1;
  54.         for (auto p : primes)
  55.         {
  56.             if (p * p * p > n)
  57.                 break;
  58.             int count = 1;
  59.             while (n % p == 0)
  60.             {
  61.                 n = n / p;
  62.                 count += 1;
  63.             }
  64.             ans = ans * count;
  65.         }
  66.         // cout<<"Con lai: "<<n<<'\n';
  67.         if (isPrime[n])
  68.             ans = ans * 2;
  69.         else if (aka(n))
  70.             ans = ans * 3;
  71.         else if (n != 1)
  72.             ans = ans * 4;
  73.         // cout<<"n: "<<n<<" and "<<"ans: "<<ans<<'\n';
  74.         if ( (ans == 4 && n!=1) || ans==3)
  75.         {
  76.             // cout << n << '\n';
  77.             res++;
  78.         }
  79.     }
  80.     cout << res;
  81.     return 0;
  82. }
Time limit exceeded #stdin #stdout 5s 31052KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yMH5wk
language:
C++14 (gcc 8.3)
created:
2 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!