Advertisement
willy108

food poisoning

Aug 12th, 2022
1,360
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.05 KB | None | 0 0
  1. //misaka and elaina will carry me to master
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <cmath>
  6. #include <utility>
  7. #include <cassert>
  8. #include <algorithm>
  9. #include <vector>
  10. #include <functional>
  11. #include <numeric>
  12. #include <set>
  13. #include <array>
  14. #include <queue>
  15. #include <map>
  16. #include <chrono>
  17. #include <random>
  18.  
  19. #define ll long long
  20. #define lb long double
  21. #define sz(vec) ((int)(vec.size()))
  22. #define all(x) x.begin(), x.end()
  23. #define pb push_back
  24. #define mp make_pair
  25. #define kill(x, s) {int COND = x; if(COND){ cout << s << "\n"; return ; }}
  26.  
  27. #ifdef ONLINE_JUDGE
  28. #define cerr while(0) cerr
  29. #endif
  30.  
  31. const lb eps = 1e-9;
  32. const ll mod = 1e9 + 7, ll_max = 1e18;
  33. //const ll mod = (1 << (23)) * 119 +1, ll_max = 1e18;
  34. const int MX = 1e6 +10, int_max = 0x3f3f3f3f;
  35.  
  36. struct {
  37.   template<class T>
  38.   operator T() {
  39.     T x; std::cin >> x; return x;
  40.   }
  41. } in;
  42.  
  43. using namespace std;
  44.  
  45. vector<int> fl;
  46. int ans[MX];
  47. int state[MX];
  48. int n, m, q;
  49.  
  50. int low[MX], primes[MX];
  51. int ind = 1;
  52.  
  53. void precomp(){
  54.     for(int i = 2; i<=n; i++){
  55.         if(low[i] == 0){
  56.             primes[ind++] = i;
  57.             for(int j = i; j<=n; j+=i){
  58.                 if(!low[j]) low[j] = i;
  59.             }
  60.         }
  61.     }
  62. }
  63.  
  64. void solve(){
  65.     n = in, m = in, q = in;
  66.     precomp();
  67.     for(int i = 1; i<=n; i++){
  68.         fl.pb(n/i);
  69.     }
  70.     sort(all(fl));
  71.     fl.resize(unique(all(fl)) - fl.begin());
  72.     for(int i = 1; i<=n; i++){
  73.         ans[i] = 1;
  74.     }
  75.     if(m < ind){
  76.         for(int j = m+1; j<ind; j++){
  77.             int x = primes[j];
  78.             for(int i : fl){
  79.                 ans[i] += ans[i/x];
  80.             }
  81.             state[x] = 1;
  82.         }
  83.     }
  84.     for(int qaq = 1; qaq <= q; qaq++){
  85.         int x = in;
  86.         x = primes[x];
  87.         if(state[x]){ //delete
  88.             reverse(all(fl));
  89.             for(int i : fl){
  90.                 ans[i] -= ans[i/x];
  91.                 assert(ans[i] > 0);
  92.             }
  93.             reverse(all(fl));
  94.         }else{ //insert
  95.             for(int i : fl){
  96.                 ans[i] += ans[i/x];
  97.             }
  98.         }
  99.         state[x] ^= 1;
  100.         cout << n - ans[n] << "\n";
  101.     }
  102. }
  103.  
  104. signed main(){
  105.   cin.tie(0) -> sync_with_stdio(0);
  106.  
  107.   int T = 1;
  108.   //cin >> T;
  109.   for(int i = 1; i<=T; i++){
  110.         solve();
  111.     }
  112.   return 0;
  113. }
  114.  
  115.  
  116.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement