ICPCCamp2017 Day 5 I Coprime Queries（莫比乌斯函数 + 容斥定理 + 二分）

题意：

给你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**/