Advertisement
Guest User

Untitled

a guest
Jun 29th, 2016
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.27 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <cmath>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. int mass[10000000]={0};
  9.  
  10. int maxDivs[10000000]={0};
  11.  
  12. const int N = 10000000;
  13. int lp[N+1];
  14. vector<int> pr;
  15.  
  16.  
  17.  
  18. int main()
  19. {
  20.  
  21.  
  22. for (int i=2; i<=N; ++i) {
  23. if (lp[i] == 0) {
  24. lp[i] = i;
  25. pr.push_back (i);
  26. }
  27. for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
  28. lp[i * pr[j]] = pr[j];
  29. }
  30.  
  31.  
  32.  
  33. int n,k;
  34.  
  35. scanf("%d %d",&n,&k);
  36.  
  37. for(int i=0;i<n;i++)
  38. scanf("%d",mass+i);
  39.  
  40. lp[1]=1;
  41.  
  42. for(int i=0;i<n;i++)
  43. {
  44. if(mass[i]==1)
  45. continue;
  46.  
  47. for(int u=lp[mass[i]];u>1;u=lp[mass[i]])
  48. {
  49. int howMuch=0;
  50. while((mass[i]%u)==0)
  51. {
  52. mass[i]/=u;
  53. howMuch++;
  54. }
  55.  
  56. maxDivs[u]=max(maxDivs[u],howMuch);
  57. }
  58. }
  59.  
  60. if(k==1)
  61. {
  62. cout<<"Yes";
  63. return 0;
  64.  
  65. }
  66.  
  67. for(int i=2;i<10000000;i++)
  68. for(int u=0;u<maxDivs[i];u++)
  69. {
  70. if(k%i==0)
  71. k/=i;
  72. }
  73.  
  74. if(k<2)
  75. cout<<"Yes";
  76. else
  77. cout<<"No";
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement