Codeforces Beta Round #85 (Div. 2 Only) D - Petya and Divisors

http://codeforces.com/contest/112/problem/D

N <= 10^5

xi <= 10^5

yi <= i - 1

N이 주어지고 N개의 줄에 걸쳐 쿼리가 주어진다. 

각 쿼리는 두 정수 xi, yi 로 이루어져있으며

xi의 약수들 중 [i - yi, i - 1] 번째 쿼리에서 주어진 xj 들을 하나도 나눌 수 없는 약수의 개수를 출력하는 것이다.

last[i] : i 가 나눌 수 있는 수의 마지막 인덱스

라고 보면 매 쿼리마다 주어지는 xi 들의 약수들을 O(root(xi) 에 모두 보면서

마지막 인덱스와 현재 인덱스와의 차이가 yi 보다 큰지 체크하면서 세어 주고

현재 인덱스로 last 를 갱신해주는 작업을 반복해주기만 하면된다.

#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios_base::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
int last[100003];
int N, x, d;
int main() {
    fastio();
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> x >> d;
        int cnt = 0;
        for(int j = 1; j * j <= x; j++){
            if(x % j) continue;
            if(last[j] + d < i) cnt++;
            if(j * j != x && last[x / j] + d < i) cnt++;
            last[j] = i;
            last[x / j] = i;
        }
        cout << cnt << "\n";
    }
    return 0;
}