2022杭电多校六 1007-Shinobu loves trip（同余方程）

题目链接：杭电多校6 - Virtual Judge

题目：

 样例输入：

2
3 2 1 1
1 1
2
5 4 3 2
1 4
4 3
2 100000
4
2

样例输出：

1
2
1

题意：多组数据，每组数据给出一个p代表国家数量，一个a，一个n代表目标旅行方案数，一个q代表询问个数，接下来n行每行给出一个s和d，s代表第i个目标旅行方案的初始国家，d代表第i个目标旅行方案的计划天数，假如当前所在城市为t，那么下一个所要去的城市就是(t*a)%p，对于每个询问，给出一个城市t，问n个目标旅行中有多少个目标会经过城市t。

我们先来看一下第i个目标的第j天所在的城市，假如第i个目标的初始城市是t，那么根据题意可得是(t*a^j)%p,假如我们现在要判断第i个目标是否包含城市x，也就是说是否有0<=j<=d[i]使得(t*a^j)%p=x成立，d[i]是第i个目标旅行方案的计划天数，这个等式等价变形为(a^j)%p=x*t^(-1)%p，那么我们就可以先预处理一下a^j%p，那么我们就知道一个数是否会在第i个目标旅行计划中出现了，但我们需要保证求出来的j是在目标旅行计划时间内的，如果超出时间那么依旧是不能到达的。所以我们就可以哈希预处理一下所有的a^j%p，这样对于每一个询问t，我们都能O(1)地确定某一个目标旅行方案是否在规定时间内包含城市t，这样就可以AC了。

注意在求解每个目标旅行方案初始城市逆元的时候可以预处理一下，要不然每个城市都会被求q次逆元，这样会TLE。

还有一个需要注意的点就是如果初始城市是0，0是没有逆元的，所以我们需要特殊处理一下，如果初始城市是0，那么他整个方案都只会在0城市，所以直接判断当前询问的城市是不是0即可。

细节见代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<unordered_map>
#include<cmath>
using namespace std;
const int N=2e6+10,M=2e5+10;
typedef long long ll;
int p,pa[N],pb[N];
unordered_map<int,int>mp;
int b[N],d[N];
int qpow(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1) ans=1ll*ans*a%p;
		a=1ll*a*a%p;
		b>>=1;
	}
	return ans;
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		mp.clear();
		int a,n,q;
		scanf("%d%d%d%d",&p,&a,&n,&q);
		pa[0]=1;mp[1]=0;
		for(int i=1;i<=M;i++)
		{
			pa[i]=1ll*pa[i-1]*a%p;
			if(!mp.count(pa[i]))
				mp[pa[i]]=i;
		}
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d",&b[i],&d[i]);
			pb[i]=qpow(b[i],p-2);
		}
		for(int i=1;i<=q;i++)
		{
			int t;
			scanf("%d",&t);
			int ans=0;
			for(int j=1;j<=n;j++)
			{
				if(b[j]==0)//注意0没有逆元，注意特判 
				{
					ans+=(t==0);
					continue;
				}
				int tt=1ll*t*pb[j]%p;
				if(!mp.count(tt)) continue;//不能到达 
				if(mp[tt]<=d[j]) ans++;//判断所需天数是否小于任务的持续天数 
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}