題意：

給你n 個數，和n 個詢問，每個詢問有l，r，x，問在區間l~r中與x互質的最大位置在哪里？

思路：

以為是個線段樹，想了好久 都沒有確切的好的思路。

其實是容斥定理。

考慮30：

質因子分解 30 = 2*3 *5

那么我們可以求出l到r中 與30 不互質的數有幾個。

很顯然那些數滿足 有2的因子或者有3 的因子或者有5的因子。是一個并集。

那么我們就加上2的個數 加上3的個數 加上5的個數 減去2*3的個數.......

很顯然  這些系數恰好是 莫比烏斯函數。

數值都是10W以內，直接跑一個10W莫比烏斯系數。進行容斥定理即可。

這樣就能快速求出一個區間內與x不互質的個數。

在考慮最大位置。

直接二分了。

m到,R區間 有的話 就更新L到m 否則 更新R到m。

詳細見代碼：

#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#define Siz(x) (int)x.size()using namespace std;const int maxn = 1e5 + 7;int mu[maxn];bool vis[maxn];int a[maxn], sum1[maxn];vector<int>fac[maxn],g[maxn];void init(){    mu[1] = 1;    for (int i = 1; i < maxn; ++i) if (mu[i]){        for (int j = i; j < maxn; j+=i)fac[j].push_back(i);        for (int j = i+i; j < maxn; j += i) mu[j]-=mu[i];    }    for (int i = 2; i < maxn; ++i){        if (mu[i])mu[i] = -mu[i];    }}void add(int x,int id){    for (int i = 0; i < Siz(fac[x]); ++i){        int v = fac[x][i];        g[v].push_back(id);    }}int calc(int l,int r,int x){    int ans = 0;    for (int i = 1; i < Siz(fac[x]); ++i){        int v = fac[x][i];        int p1 = lower_bound(g[v].begin(),g[v].end(),l)-g[v].begin();        int p2 = lower_bound(g[v].begin(),g[v].end(),r+1)-g[v].begin();        ans += mu[v] * (p2-p1);    }    return r-l+1 - (ans);}int solve(int l,int r,int x){    if(calc(l,r,x) == 0) return -1;    int L = l,R = r;    int ans;    while(L < R){        int m = L+R>>1;        if (calc(m+1,R,x))L = m+1;        else R = m;    }    return L;}int main(){    init();    int n,q;    while(~scanf("%d %d",&n, &q)){        sum1[0] = 0;        for (int i = 0; i < maxn; ++i)g[i].clear();        for (int i = 1; i <= n; ++i){            scanf("%d",&a[i]);            sum1[i] = sum1[i-1];            if (a[i] == 1){                sum1[i]++;            }            add(a[i],i);        }        while(q--){            int l,r,x;            scanf("%d %d %d",&l, &r, &x);            if (x == 1) PRintf("%d/n",r);            else{                int ans = solve(l,r,x);                printf("%d/n",ans);            }        }    }    return 0;}/**5 41 2 3 4 61 5 21 1 14 5 23 5 3**/