fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define MAX 100000
  5.  
  6. int factors[MAX+5];
  7. int primeFactor[MAX+5];
  8.  
  9. void sieve()
  10. {
  11. int i, j;
  12.  
  13. primeFactor[1] = 1;
  14.  
  15. primeFactor[2] = 2;
  16. for (i = 4; i <= MAX; i+=2)
  17. primeFactor[i] = 2;
  18.  
  19. for (j = 3; j <= MAX; j+=2)
  20. {
  21. if (primeFactor[j] == 0)
  22. {
  23. primeFactor[j] = j;
  24. for (i = j*j; i <= MAX; i+=j)
  25. {
  26. if (primeFactor[i] == 0)
  27. {
  28. primeFactor[i] = j;
  29. }
  30. }
  31. }
  32. }
  33.  
  34. }
  35.  
  36. int main()
  37. {
  38. #ifdef VSP4
  39. freopen("input.txt", "r", stdin);
  40. freopen("output.txt", "w", stdout);
  41. #endif // VSP4
  42.  
  43. int N, Q, i, j, k, x, ans, last, count;
  44.  
  45. sieve();
  46.  
  47. cin >> N;
  48.  
  49. for (i = 0; i < N; i++)
  50. {
  51. cin >> x;
  52. while (x != 1)
  53. {
  54. factors[primeFactor[x]]++;
  55. x /= primeFactor[x];
  56. }
  57. }
  58.  
  59. cin >> Q;
  60. for (i = 0; i < Q; i++)
  61. {
  62. cin >> x;
  63. ans = 1e9;
  64. map<int, int> tempMap;
  65. while (x != 1)
  66. {
  67. tempMap[primeFactor[x]]++;
  68. x /= primeFactor[x];
  69. }
  70. for (auto it: tempMap)
  71. {
  72. ans = min(ans, factors[it.first]/it.second);
  73. }
  74. cout << ans << "\n";
  75. }
  76.  
  77. return 0;
  78. }
  79.  
Runtime error #stdin #stdout 0s 4240KB
stdin
Standard input is empty
stdout
Standard output is empty