HDU 5768 Lucky7 2016多校第四场1005

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5768
题意：给你一个范围和n个ai、pi，让你找出在范围内模ai等于pi，并且为7的倍数的数，输出他们的数量。
题解：中国剩余定理模板题，加上容斥处理。
中国剩余定理相关：http://blog.csdn.net/acdreamers/article/details/8050018。
中国剩余定理也就是把一系列模线性方程拼成一个方程来求解。用容斥防止爆long long。

那么问题转化为求范围内x的个数。那么对于这个模线性方程，我们先设两个相邻的成立的x分别为a、b（a<b）,那么a、b的关系肯定是b=a+M,也就是说每一个长度为M的区间有且仅有一个x。那么问题转为求区间内长度为M的区间的个数。注意最后剩余区间（长度不满足M）也可能存在x。

代码如下：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int T;
int n;
ll ta[20],tp[20];
ll lw,he;

void ex_gcd(ll a,ll b,ll &x,ll &y)
{
	if(!b)
	{
		x=1,y=0;
		return;
	}
	ex_gcd(b,a%b,y,x);
	y-=x*(a/b);
}

//ll mul_mod(ll x,ll y,ll mod)
//{
//	ll ans=0;
//	while(y)
//	{
//		if(y&1)
//			ans=(ans+x)%mod;
//		x=(x+x)%mod;
//		y>>=1;
//	}
//	return ans;
//}

ll CRT(const ll tmp)
{
	int st=(1<<n);
	int cnt;
	ll ret=0;
	for(int i=1;i<st;i++)
	{
		cnt=0;
		ll ans=0;
		ll M=7;
		for(int j=0;j<n;j++)
			if(i&(1<<j))
				M*=tp[j],cnt++;
		for(int j=0;j<n;j++)
		{
			ll x=0,y=0;
			if(i&(1<<j))
			{
				ll mi=M/tp[j];
				ex_gcd(mi,tp[j],x,y);
				x=((x%tp[j])+tp[j])%tp[j];
				ans=(ans+((((x%M)*(ta[j]%M)%M)*(mi%M))%M)%M)%M;
				ans=(ans%M+M)%M;
			}
		}
		ans=(ans%M+M)%M;
		ll tem=tmp/M;//求出区间内M的倍数的个数
		if(tmp%M>=ans)//考虑剩余部分。
			tem++;
		if(cnt&1)
			ret+=tem;
		else
			ret-=tem;
	}
	return ret;
}

int main()
{
	freopen("in.txt","r",stdin);
	scanf("%d",&T);
	for(int kase=1;kase<=T;kase++)
	{
		scanf("%d%I64d%I64d",&n,&lw,&he);
		for(int i=0;i<n;i++)
			scanf("%I64d%I64d",tp+i,ta+i);
		lw--;
		ll tot=he/7-lw/7;
		printf("Case #%d: %I64d
",kase,tot-CRT(he)+CRT(lw));
	}
	return 0;
}