fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define Seny ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. #define all(v) v.begin(),v.end()
  5. #define print(v) for(auto q : v)cout<<q<<" "
  6. #define ll long long
  7. const int mod = 1e9 + 7;
  8. //const int N = 1e6;
  9.  
  10. map<int,int>all;
  11.  
  12. void pre(int N)
  13. {
  14.     for (int i = 2; i <= N; ++i) {
  15.         int tmp = i;
  16.         for (int j = 2; j*j <= i; ++j) {
  17.             while (tmp % j == 0)
  18.             {
  19.                 all[j]++;
  20.                 tmp/=j;
  21.             }
  22.         }
  23.         if(tmp > 1)
  24.             all[tmp]++;
  25.     }
  26.     return;
  27. }
  28.  
  29. void solve() {
  30.     int n,q;cin >> n >> q;
  31.     pre(n);
  32.     while (q--)
  33.     {
  34.         int op,x;cin >> op >> x;
  35.         if(op == 1)
  36.         {
  37.             int tmp = x;
  38.             for (int i = 2; i*i <= x; ++i) {
  39.                 while (tmp % i == 0)
  40.                 {
  41.                     all[i]++;
  42.                     tmp/=i;
  43.                 }
  44.             }
  45.             if(tmp > 1)
  46.                 all[tmp]++;
  47.         }
  48.         else
  49.         {
  50.             map<int,int>check;
  51.             int tmp = x;
  52.             for (int i = 2; i*i <= x; ++i) {
  53.                 while (tmp % i == 0)
  54.                 {
  55.                     check[i]++;
  56.                     tmp/=i;
  57.                 }
  58.             }
  59.             if(tmp > 1)
  60.                 check[tmp]++;
  61.             int ans = 1e9;
  62.             for(auto i : check)
  63.             {
  64.                 ans = min(ans,(int)floor((double)all[i.first]/i.second));
  65.             }
  66.             cout << ans <<'\n';
  67.         }
  68.     }
  69. //    for(auto i :all)
  70. //    {
  71. //        cout << i.first<<" "<<i.second;
  72. //    }
  73. }
  74.  
  75. signed main() {
  76.     Seny
  77.     int t = 1;
  78.     //cin >> t;
  79.     while (t--)
  80.         solve();
  81. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/YtOM5z
language:
C++ (gcc 8.3)
created:
84 days 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!