# LISGCD

## Đề bài

Cho số nguyên $n$ và $n$ số nguyên $a_1,a_2,…,a_n$. Đếm số lượng dãy không rỗng $(a_{b_m})$ thỏa mãn:
+ $b_1≤b_2≤⋯≤b_m$
+ $a_{b_1} \le a_{b_2} \le … \le a_{b_m}$
+ $gcd(a_{b_1},a_{b_2},…,a_{b_m})=1$

Vì kết quả có thể rất lớn, modulo cho $10^9+7$.

## Input:

- Dòng đầu chứa số $n$ ($1 \le N \le 10^{5}$).
- Dòng tiếp theo gồm $n$ số nguyên $a_1,a_2,…,a_n$ ($1 \le a_i \le 10^5$).

## Output

- Gồm một số duy nhất là số dãy con thỏa mãn modulo $10^9+7$.

## Sample


## Giới hạn

- Subtask 1:($30\%$) $1 \le n, a_i \le 300$.
- Subtask 2:($30\%$) $1 \le a_i \le 300$.
- Subtask 3:($40\%$) Không có điều kiện gì thêm.

## Lời giải:

<details>
<summary>Lời giải</summary>

- Gọi $dp[i]$ là số dãy con tăng có ước chung lớn nhất là bội của $i$.
Xét dãy $c$ là dãy gồm tất cả các số chia hết cho $i$ trong dãy ($a_n$). Để tính số dãy con tăng của dãy $c$, ta sử dụng thuật toán Fenwick Tree.
- Gọi $f[i]$ là số dãy con tăng có ước chung lớn nhất là $i$.
CT: $f[i] -= dp[j]$ (với $j$ là bội của $i$).
- Đáp số: $f[1] \% (10^9+7)$
- ĐPT: $O(n \times log^2(n))$

</details>

<details>
<summary>Code: </summary>

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define fi first
#define se second
#define pii pair<ll, ll>

ll n, res, dem, mod = 1e9 + 7;
ll luu[100005], nt[100005];
ll dp[100005], t, BIT[100005], b[100005];
vector <ll> a;
vector < vector <ll> > d;

ll cong (ll x, ll y) {
    ll ans = x + y;
    if (ans >= mod) return ans - mod;
    if (ans < 0) return ans + mod;
    return ans;
}

ll mu (ll x) {
    if (x == 0) return 1;
    ll ans = mu(x / 2);
    if (x % 2 == 0) return ans * ans % mod;
    return ans * ans % mod * 2 % mod;
}

void update (ll x, ll val) {
    for (; x <= 1e5; x += x & -x)
        BIT[x] = cong(BIT[x], val);
}

void ud (ll x, ll val) {
    for (; x <= 1e5; x += x & -x)
        BIT[x] = val;
}

ll get(ll x) {
    ll ans = 0;
    for (; x > 0; x -= x & -x)
        ans = cong(ans, BIT[x]);
    return ans;
}

void Add (ll x, ll vt) {
    luu[0] = 1;
    a.clear();
    a.push_back(1);
    d[1].push_back(vt);
    while (x > 1) {
        ll k = nt[x];
        dem = 0;
        while (x % k == 0) {
            x = x / k;
            dem++;
            luu[dem] = luu[dem - 1] * k;
        }
        ll l = a.size();
        for (ll i = 0; i < l; i++)
        for (ll j = 1; j <= dem; j++) {
            a.push_back(luu[j] * a[i]);
            d[luu[j] * a[i]].push_back(vt);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    d.resize(1e5);
    for (ll i = 2; i <= 1e5; i++)
        if (nt[i] == 0) {
            nt[i] = i;
            for (ll j = i; j <= 1e5 / i; j++) 
                nt[i * j] = i;
        }
    for (ll i = 1; i <= n; i++) {
        cin >> b[i];
        Add(b[i], i);
    }
    
    for (ll i = 1; i <= 1e5; i++) {
        ll l = d[i].size();
        for (ll j = 0; j < l; j++) {
            ll m = b[d[i][j]];
            ll val = get(m) + 1;
            dp[i] = cong(dp[i], val);
            update(m, val);
        }
        for (ll j = 0; j < l; j++) {
            ll m = b[d[i][j]];
            ud(m, 0);
        }
    }
                             
    for (ll i = 1e5; i >= 1; i--) {
        for (ll j = 2; j <= 1e5 / i; j++)
            dp[i] = cong(dp[i], -dp[j * i]);
    }
                              
    cout << (dp[1] + mod) % mod;
                 
    return 0;
}

</details>