3362 - 约数和

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

2

Hint

【样例解释】

两序列分别为

7 2 3 2

24 3 2 3

所以最长公共上升长度为2

【数据范围】

每个质因子小于等于100，质因子个数小于等于50，可以分解出每个质因子个数小于等于50，m≤5000，a,b,c,d≤1000

Solution C++

#include<cstdio>
#include<cstring>
#include<algorithm>

#define mod 1222

typedef long long ll;

using namespace std;

ll n,m,a,b,c,d;
ll x,y;
ll px[5010];
ll qy[5010];
ll f[5010];

int quick_pow(int x,int k){
	int ans=1;
	
	while(k>0){
		if(k&1){
			ans=ans*x%mod;
		}
		x=x*x%mod;
		k>>=1;
	}
	
	return ans%mod;
}

int main(){
	//freopen("ysh.in","r",stdin);
	//freopen("ysh.out","w",stdout);
	
	memset(qy,0,sizeof(qy));
	memset(px,0,sizeof(px));
	px[1]=1;qy[1]=1;
	
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%lld%lld",&x,&y);
		int tot=0;
		
		for(int j=0;j<=y;++j){
			tot+=quick_pow(x,j)%mod;
		}
		px[1]*=tot;
		px[1]%=mod;
	}
	
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%lld%lld",&x,&y);
		int tot=0;

		for(int j=0;j<=y;++j){
			tot+=quick_pow(x,j)%mod;
		}
		qy[1]*=tot;
		qy[1]%=mod;
	}

	scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
	
	scanf("%lld",&m);
	
	for(int i=2;i<=m;++i){
		px[i]=(a*px[i-1]*px[i-1]%d+b*px[i-1]%d+c%d)%d;
		qy[i]=(a*qy[i-1]*qy[i-1]%d+b*qy[i-1]%d+c%d)%d;
	}
	/*
	for(int i=1;i<=m;++i){
		cout<<px[i]<<" ";
	}
	cout<<endl;
		for(int i=1;i<=m;++i){
		cout<<qy[i]<<" ";
	}
	cout<<endl;
	*/
	for(int i=1;i<=m;++i){
		int maxx=0;
		for(int j=1;j<=m;++j){
			if(px[i]>qy[j]&&f[j]>maxx){
				maxx=f[j];
			}
			if(px[i]==qy[j]&&f[j]<maxx+1){
				f[j]=maxx+1;
			}
		}
	}
	
	sort(f+1,f+m+1);
	
	printf("%lld",f[m]);
	
	fclose(stdin);
	fclose(stdout);
}