PS와 개발을 공부하자

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

Algorithm/Problem Solving

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

sgc109 2017.07.30 11:15

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 를 갱신해주는 작업을 반복해주기만 하면된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
}
cs


0 Comments
댓글쓰기 폼