FreakSkipper

F. Ovos Veras

Oct 30th, 2020 (edited)
731
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define vi vector<int>
  6. #define ll long long
  7. #define pb push_back
  8. #define mp make_pair
  9. #define ii pair<int, int>
  10.  
  11. vi all_divisors(int n, int x) {
  12.     vi ans;
  13.  
  14.     for (int i = 1; i * i <= x && i <= n; i++) {
  15.         if (x % i == 0) {
  16.             int b = x / i;
  17.             ans.emplace_back(i);
  18.             if (i != b && b <= n) {
  19.                 ans.emplace_back(b);
  20.             }
  21.         }
  22.     }
  23.     sort(ans.begin(), ans.end());
  24.  
  25.     return ans;
  26. }
  27.  
  28. vector<vi> all_divisors_until_n(int n) {
  29.     vector<vi> ans(n + 1);
  30.  
  31.     for (int i = 1; i <= n; i++) {
  32.         // ans.emplace_back(all_divisors(i));
  33.     }
  34.  
  35.     return ans;
  36. }
  37.  
  38. int main() {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(NULL);
  41.  
  42.     int m, n;
  43.     scanf("%d %d", &m, &n);
  44.  
  45.     vi amigos(n + 1, 0);
  46.  
  47.     for (int q = 1; q <= m; q++) {
  48.         int x, y;
  49.         scanf("%d %d", &x, &y);
  50.  
  51.         int ovos = 0;
  52.         vi divs = all_divisors(n, x);
  53.        
  54.         for (auto &e : divs) {
  55.             if (y <= q - 1 - amigos[e]) {
  56.                 amigos[e] = q;
  57.                 ovos++;
  58.             }
  59.         }
  60.  
  61.         printf("%d\n", ovos);
  62.     }
  63.  
  64.     return 0;
  65. }
RAW Paste Data