「2015四校联考-nodgd」无聊的计算 - 数论

题目大意

给两个序列$a[]$，$b[]$，求出$a_i^{b_j}\%p\le q$的二元组$(i,j)$组数。

---

初步想法

如果直接枚举$i$与$j$肯定超时，然而观察到模数$p\le$ 5000，对于这种模数比较小的我们一般思路是把原数通过模转化为模数范围内再做处理。
根据同余模定理，$a_i^{b_j}\%p=(a_i\%p)^{b_j}\%p$。
那么我们只需要考虑将$b[]$降到$p$范围内。
根据费马小定理$a_i^{p-1}\%p=1$，代入即可得到$a_i^{b_j}\%p=a_i^{b_j\%(p-1)}\%p$。
于是我们即可把$a[]$和$b[]$的范围降到$p$内，用$O(n^2)$的枚举解决。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
LL p,q,n,m,a[1000005],b[1000005],A,B,C,D,E,F,cnt1[5005],cnt2[5005],ans=0;
int main() {
	p=Get_Int();
	q=Get_Int();
	n=Get_Int();
	a[1]=Get_Int()%p;
	a[2]=Get_Int()%p;
	cnt1[a[1]]++,cnt1[a[2]]++;
	A=Get_Int();
	B=Get_Int();
	C=Get_Int();
	for(int i=3; i<=n; i++) {
		a[i]=(((A*a[i-1])%p-(B*a[i-2])%p-C)%p+p)%p;
		cnt1[a[i]]++;
	}
	m=Get_Int();
	b[1]=Get_Int()%(p-1);
	b[2]=Get_Int()%(p-1);
	cnt2[b[1]]++,cnt2[b[2]]++;
	D=Get_Int();
	E=Get_Int();
	F=Get_Int();
	for(int i=3; i<=m; i++) {
		b[i]=(((D*b[i-1])%(p-1)+(E*b[i-2])%(p-1)+F)%(p-1)+(p-1))%(p-1);
		cnt2[b[i]]++;
	}
	for(int i=0; i<p; i++) {
		int sum=1;
		for(int j=0; j<p-1; j++) {
			if(sum<=q)ans+=cnt1[i]*cnt2[j];
			sum=sum*i%p;
		}
	}
	printf("%lld\n",ans);
	return 0;
}