Advertisement
Zeinab_Hamdy

Untitled

Apr 3rd, 2024
753
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.38 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define nl "\n"
  4. #define fi first
  5. #define se second
  6. #define pb push_back
  7. #define ll long long
  8. #define ull unsigned ll
  9. #define RV  return void
  10. #define sz(x) int(x.size())
  11. #define all(v) v.begin(), v.end()
  12. #define rall(v) v.rbegin(), v.rend()
  13. #define fixed(n) fixed << setprecision(n)
  14. #define cin(v) for (auto&i:v) cin >> i;
  15. #define cout(v) for (auto&i:v) cout << i << " ";
  16. #define clr(memo, x) memset(memo, x, sizeof memo)
  17. #define FastCode ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  18.  
  19. void  Zainab(){
  20.             // #ifndef ONLINE_JUDGE
  21.               // freopen("hobz.in", "r", stdin);
  22.               // freopen("longpath.out", "w", stdout);
  23.             // #endif
  24. }
  25.  
  26. const ll N = 1e6 ;
  27. ll spf[N+5];
  28. void mod_Sieve(){
  29.    iota(spf , spf +N+5 , 0);
  30.    spf[0]=spf[1]=-1;
  31.  
  32.    for(ll i = 2 ; i * i <= N ; i++)
  33.         if(spf[i]==i)
  34.             for(ll j = i * i ; j <= N ; j+=i)
  35.                 if(spf[j]==j)
  36.                     spf[j]=i;
  37.    
  38. }
  39.  
  40.  
  41. void myCode( ){
  42.  
  43. ll q ;
  44. cin >> q;
  45. mod_Sieve();
  46. map < ll , ll > mp ;
  47. ll last =1;
  48.  
  49.  
  50.  
  51. while(q--){
  52.     int op ; cin >> op;
  53.     if(op==1){
  54.         ll x ;     cin >> x;
  55.        
  56.         while(x > 1){
  57.             mp[spf[x]]++;
  58.             x/= spf[x];
  59.         }
  60.      
  61.     }
  62.  
  63.     else{
  64.  
  65.        
  66.         ll x ;     cin >> x;
  67.         if(x <= last) {
  68.             cout << "YES\n";
  69.             continue;
  70.         }
  71.        
  72.        
  73.         bool flag = 0;
  74.         for(ll i =last+1 ; i <= x ; i++){
  75.             ll t = i;
  76.             while(t > 1){
  77.                 if(mp[spf[t]] > 0){
  78.                     mp[spf[t]]--;
  79.                 }
  80.                 else {
  81.                     // cout << t << " " << spf[t] << nl;
  82.                     cout << "NO\n";
  83.                     flag=1;
  84.                     break;
  85.                 }
  86.                
  87.                 t/=spf[t];
  88.             }
  89.            
  90.             if(flag) break;
  91.             last = max(last , i);
  92.         }
  93.        
  94.         if(!flag) cout << "YES\n";
  95.        
  96.     }
  97. }
  98.  
  99.  
  100. // for(auto& [f,s] : mp) cout << f << " " << s << nl;
  101.  
  102.  
  103. }
  104.  
  105.  
  106. int main(){
  107.                                    FastCode ;
  108.                                    // Zainab();
  109.  
  110.     int testCase=1;
  111.     //   cin >> testCase ;
  112.       for(int i=1 ; i<= testCase ; i++)
  113.         myCode();
  114.  
  115.     return 0;
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement