description：

给出一个包含k个全素数序列A 对于一个数x A中没有x的因子 则称x与A无关 问区间L,R中包括多少个与A无关的数

solution：

L,R的范围很大 1e18 暴力肯定不可取 观察到k的范围很小 从k入手 考虑生成1~k的全排列 复杂度爆炸
考虑容斥原理 由于每个Ai都是素数 所以对于 x 是a[i]的倍数为 x/a[i]个 对于Ai 和 Aj 则为 x / (a[i] * a[j]) 个 ...
所以不为ai倍数个数为 x - x / a[i]

用递归求出倍数个数 利用前缀和思想 把答案转换为 dfs(r) - dfs(l - 1） 即可 复杂度图片说明

code:

#include <bits/stdc++.h>

using namespace std;

#define LL long long

int a[25],k;

LL dfs(int dep,LL x){
    if(dep == k){
        return x;
    }
    return dfs(dep + 1,x) - dfs(dep + 1,x / a[dep]);
}

int main(){
    LL l,r;

    cin >> l >> r >> k;

    for(int i = 0;i < k;i ++){
        cin >> a[i];
    }

    cout << dfs(0,r)  - dfs(0,l - 1) << '\n';

    return 0;
}