2017 SCPC 예선 2차 Divisor

\(N,M\le{10^5}\)

인덱스 이외의 모든수는 \({10^6}\) 이하의 자연수

N개의 수로 이루어진 A[i] 가 주어지고, M개의 쿼리가 주어지는데 각 쿼리는 b, l, r 로 이루어지며

구해야 할 것은 b의 약수들 중에 \(A_l, A_{l+1}, \dots, A_r\) 들을 모두 나눌 수 없는 약수들의 수 이다.

이 각 쿼리들의 결과를 모두 합한 값을 출력하는 문제이다.

어차피 각 수는 10^6 이하이기 때문에 이런 배열을 하나 만들 수 있다.

last[i] : i로 나눌 수 있는 최대 인덱스

그럼 오프라인으로 각 쿼리를 r 로 오름 차순 정렬한뒤 하나하나 봐주면서 현재 쿼리의 r까지 

A[i]의 약수들에 대해 last[약수] 를 i로 업뎃해준다. 그런뒤 b의 약수들에 대해 last[약수] 가 l보다 크거나 같은지

체크한다. A[r] 까지 last를 업뎃해줬을 때 last[i]가 l보다 크거나 같다는건

A에서 [l, r] 에 있는 어떤 수를 i가 나눌 수 있다는 뜻이기 때문이다. 좀더 직관적으로 말하면

i가 [l, r] 범위내에 있는 A원소 중 어떤 한놈의 약수라는 뜻이다. 만약 l보다 작다면

A[0] 부터 A[r] 까지 아직 i를 약수로 갖는 놈이 안나왔거나 l보다 작은 인덱스의 놈이라는 뜻인것이다.

비슷한 문제는 http://codeforces.com/contest/112/problem/D    풀이

#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const ll infl = 0x3c3c3c3c3c3c3c3c;
 
struct Query{
    int b, l, r;
    bool operator<(const Query& rhs) const{
        return r < rhs.r;
    }
};
vector<int> calcDivs(int x){
    vector<int> ret;
    for(int i = 1; i * i <= x; i++){
        if(x % i) continue;
        ret.pb(i);
        if(i * i != x) ret.pb(x / i);
    }
    return ret;
}
int A[100003];
int last[1000003];
int T, N, M;
vector<Query> qs;
int main() {
    fastio();
    cin >> T;
    for(int t = 1; t <= T; t++){
        memset(last,-1,sizeof(last));
        qs.clear();
        cin >> N >> M;
        for(int i = 0 ; i < N; i++) cin >> A[i];
        for(int i = 0 ; i < M; i++){
            int b, l, r;
            cin >> b >> l >> r;
            l--, r--;
            qs.pb(Query{b, l, r});
        }
        sort(all(qs));
        int prv = -1;
        int ans = 0;
        for(auto q : qs){
            int b = q.b;
            int l = q.l;
            int r = q.r;
            for(int i = prv + 1; i <= r; i++){
                int x = A[i];
                vector<int> divs = calcDivs(x);
                for(int dv : divs){
                    last[dv] = i;
                }
            }
            vector<int> divs = calcDivs(b);
            for(int dv : divs){
                if(last[dv] < l) ans++;
            }
            prv = r;
        }
        cout << "Case #" << t << '\n';
        cout << ans << '\n';
    }
    return 0;
}