HDU Lucky7(容斥+中國剩餘定理 + 快速加 + 二進制壓位)

給你一個區間，問你在這個區間内 不滿足模m[i]等于a[i]的 并且能被7整除的個數有幾個

我們先求一下在這個區間裡的 7 的倍數有多少個，

然後在求 是 7 的倍數，然後又滿足 模 m[i] 等于 a[i]  的有多少個，

由于 m[i],a[i] 有 n 個，但是 n 又不超過 15 個，是以我麼可以用充斥原理來求，

奇數就 -  偶數 就 + 。

把  m[i],a[i] 的情況用二進制枚舉一下，用中國剩餘定理求他們的最小的公共數是多少。然後 

再求 區間裡一共有多少個。

主要熟悉一下中國剩餘定理求解線性同餘方程。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mem(x,v) memset(x,v,sizeof(x))
using namespace std;
typedef long long LL;
LL m[20],a[20];
LL s[20];
LL n,x,y;
void exgcd(LL a, LL b, LL &x,LL &y){
	if (b == 0){
		x = 1; y = 0; return ;
	}
	exgcd(b,a%b,x,y);
	LL tmp = x;
	x = y; y = tmp - a / b * y;
	return ;
}
LL mul(LL a, LL k, LL M){
	LL res = 0;
	while(k){
		if (k & 1) res = (res + a)%M;
		k >>= 1;
		a = (a << 1)%M;
	}
	return res;
}
LL China(){
	LL ans = 0,res,M = 1;
	for (int i = 0; i <= n; i++){
		if (s[i]) M *= m[i];
	}
	for (int i = 0; i <= n; i++){
		if (s[i]){
		    LL x,y;
		    LL Mi = M / m[i];
			exgcd(Mi,m[i],x,y);
			x = (x % m[i] + m[i])% m[i];
			ans = ((ans + mul(a[i]*Mi,x,M)%M)+M)%M;
		}
		
	}
    res = (y + M - ans)/M - (x - 1 + M - ans)/M;//所有符合條件的解為ans = x+k*M，
    //可以知道在[1，y]這個區間内，有（M+y-x）/ M個k符合條件，
    return res;
}

void init(){
	cin>>n>>x>>y;
    for (int i = 0; i < n; i++)
    	scanf("%I64d%I64d",&m[i],&a[i]);
    m[n] = 7; a[n] = 0; s[n] = 1;
    return;
}


int main(){
    int T,num = 1;
    cin>>T;
    while(T--){
    	init();
    	LL ans = 0;
    	for (int i = 0; i < (1 << n); i++){ //二進制壓縮。
    		int k = 0;
    		for (int j = 0; j < n; j++){
    			if (i & (1 << j)) s[j] = 1,k++; else s[j] = 0;
    		}
    		k = k & 1 ? -1 : 1; //這裡用到了容斥原理。奇數 -，偶數 +。
    		ans += China()*k;	//i 一定從 0 開始，0 是算 7 的倍數的。
    	}
    	printf("Case #%d: ",num++);
    	printf("%I64d\n",ans);
    }


	return 0;
}