fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define MAXN   10000001
  4. long long int power(long long int a,long long int b)
  5. {
  6. if(b==1)
  7. return a;
  8. else
  9. return a*power(a,b-1);
  10. }
  11. long long int spf[MAXN];
  12. void sieve()
  13. {
  14.     spf[1] = 1;
  15.     for (long long int i=2; i<MAXN; i++)
  16.         spf[i] = i;
  17.  
  18.     for (long long int i=4; i<MAXN; i+=2)
  19.         spf[i] = 2;
  20.  
  21.     for (long long int i=3; i*i<MAXN; i++)
  22.     {
  23.  
  24.         if (spf[i] == i)
  25.         {
  26.  
  27.             for (long long int j=i*i; j<MAXN; j+=i)
  28.  
  29.                 if (spf[j]==j)
  30.                     spf[j] = i;
  31.         }
  32.     }
  33. }
  34.  
  35. vector<long long int> getFactorization(long long int x)
  36. {
  37.     vector<long long int> ret;
  38.     while (x != 1)
  39.     {
  40.         ret.push_back(spf[x]);
  41.         x = x / spf[x];
  42.     }
  43.     return ret;
  44. }
  45.  
  46. int main()
  47. {
  48. sieve();
  49. long long int t;
  50. cin>>t;
  51. while(t--)
  52. {
  53. long long int n;
  54. cin>>n;
  55. long long int val;
  56. vector<long long int> v;
  57. for(long long int i=0;i<n;i++)
  58. {
  59. cin>>val;
  60. v.push_back(val);
  61. }
  62. map<long long int,long long int> m;
  63. for(long long int i=0;i<n;i++)
  64. {
  65. vector<long long int> vec=getFactorization(v[i]);
  66. for(long long int j=0;j<vec.size();j++)
  67. {long long int p=1;
  68. while((v[i]%(long long int)power(vec[j],p)==0))
  69. {
  70. m[v[i]]++;
  71. p++;
  72. }
  73. }
  74. for(long long int j=i+1;j<n;j++)
  75. {
  76. for(long long int k=0;k<vec.size();k++)
  77. {
  78. if(v[j]%vec[k]==0)
  79. {
  80. v[j]/=vec[k];
  81. m[vec[k]]++;
  82. }
  83. }
  84. }
  85. }
  86. long long int prod=1;
  87. map<long long int,long long int>::iterator i;
  88. for(i=m.begin();i!=m.end();i++)
  89. if(i->first!=1)
  90. prod*=(i->second+1);
  91. cout<<prod<<endl;
  92. }
  93. }
  94.  
  95.  
  96.  
  97.  
Time limit exceeded #stdin #stdout 5s 4275740KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/64Tmmy
language:
C++14 (gcc 8.3)
created:
4 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!