首页 > 代码库 > zoj 3233 容斥原理 + 双条件

zoj 3233 容斥原理 + 双条件

2024-07-04 17:52:34   227人阅读

题目来源：

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3490

题意：  给出两个集合Y , N , 给出区间【low , high】 , 问在 这个区间有多少个这样的数，x ，  满足， 集合Y中至少一个数被x 整除， 且 集合 N中至少一个数不被x 整除。

分析：两个条件

Q1 ：  集合Y中至少一个数被x 整除 ， 满足这个条件的个数为 A；

Q2 :  集合 N中至少一个数不被x 整除。 满足这个条件的个数为B

集合 s = {1 ,2 ,....n} 中 满足 这两个条件的个数， 为 ：  A ∩ B = A - （A- B） = A - (A ∩  ? B) 

非B  表示，  满足 条件  集合N中 所有数被 x  整除的   ， 这样 x 的个数。

所以在 计算 每个节点的个数时 ， 使用 这个函数

LL cel(LL a, LL num){
return num / a - num / LCM(a , lcm) ;
}

代码如下：

using namespace std ;
const double EPS = 1e-16 ;
typedef long long LL ;
const int Max_N =  505;
const double inf = 1e10 ; // 这个 开小了 1e9 都WA了好几次
int n , m;
LL low , high , lcm  , a[Max_N] , b ;
LL GCD(LL x, LL y){
    return y == 0 ? x : GCD(y , x % y) ;
}
LL LCM(LL x, LL y){ // 处理巧妙，防止越界
    LL g;
    g = GCD(x , y) ;
    if(x / g > high / y)
        return high + 1 ;
    return x / g * y ;
}
LL cel(LL a,  LL num){
    return num / a - num / LCM(a , lcm) ;
}
void dfs(int now , int Count , LL lcm_1 , LL &sum , LL num){
    lcm_1 = LCM(a[now] , lcm_1) ;
    if(Count & 1)
        sum += cel(lcm_1 , num);
    else sum -= cel(lcm_1 , num);
    for(int i = now + 1 ; i < n ; i++){
        dfs(i , Count +1 , lcm_1 , sum , num ) ;
    }
}
void ok(){
    LL sum1 = 0 ,sum2  = 0;
    int i;
    for(i = 0 ; i < n ;i++){
        dfs(i, 1 , a[i] , sum1 , high) ;
    }
    for(i = 0 ; i < n ;i++){
        dfs(i, 1 , a[i] , sum2 , low -1) ;
    }
    printf("%lld\n" , sum1 - sum2) ;
}
int main(){
    int i ;
    while(cin>>n >> m >> low >> high){
        lcm = 1 ;
        if(n == 0 && m ==0 && low == 0 && high == 0) break ;
        for(i = 0 ; i < n ; i++)
            scanf("%lld" , &a[i]) ;
        for(i = 0 ; i < m ; i++){
            scanf("%lld" , &b) ;
            lcm = LCM(lcm , b) ;
        }
        ok() ;
    }
}

 


联系
我们