文章目录

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5768
题意：给n组数，每组有个m 和 r ，求[L,R]范围内满足x是7的倍数，并且不满足任意一个 x % m i = r i x\% m_i =r_i x%mi​=ri​的个数
同余方程的模板

ans=满足0个-满足1个+满足两个-满足3个。。。。。

#include"bits/stdc++.h"
#include"iostream"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
const LL inf=1e18;
LL exgcd(LL a, LL b, LL &x, LL &y,LL c)
{
	if (b == 0)
	{
		x = c;
		y = 0;
		return a;
	}
	LL d = exgcd(b, a % b, x, y,c);
	LL t = x;
	x = y;
	y = t - a / b * y;
	return d;
}
pair<LL,LL> calc(pair<LL,LL> p1,pair<LL,LL> p2)//计算两个同余方程组，返回的也是pair
{
	LL m1=p1.first,r1=p1.second;
	LL m2=p2.first,r2=p2.second;
	LL x,y;
	LL d=exgcd(m1,m2,x,y,1);
	if((r2-r1)%d)return make_pair(inf,inf);//无解情况
	LL lcm=m1/d*m2;
	x*=(r2-r1)/d;
	x%=lcm/m1;//x可能太大，模一下
	LL res=m1*x+r1;
	res=(res%lcm+lcm)%lcm;
	return make_pair(lcm,res);
}
pair<LL,LL>a[maxn];//用pair封装，first是模数，second是余数
int N;
LL solve(LL n)
{
	if(n<7)return 0;
	LL ans=0;
	for(int sta=0; sta<(1<<N); sta++)
	{
		pair<LL,LL> tp=make_pair(7,0);
		for(int i=0; i<N; i++)
		{
			if(sta&(1<<i))tp=calc(tp,a[i]);
		}
		LL t=0;
		if(tp.second>0&&tp.second<=n)t++;//如果余数是在范围内，就那么这个数要计算上 
		t+=(n-tp.second)/tp.first;		//还要加上k*lcm+r 
		if(__builtin_popcount(sta)%2==0)ans+=t;
		else ans-=t;
	}
	return ans;
}
int main()
{
	LL T,L,R;
	cin>>T;
	for(int Case=1; Case<=T; Case++)
	{
		cin>>N>>L>>R;
		for(int i=0; i<N; i++)
		{
			LL t1,t2;
			cin>>t1>>t2;
			a[i]=make_pair(t1,t2);
		}
		cout<<"Case #"<<Case<<": "<<solve(R)-solve(L-1)<<endl;
	}
}
/* 1 1 1 100000000000000000 11 2 */