LOJ#3096. 「SNOI2019」数论

如果\(P > Q\)我们把\(P\)和\(Q\)换一下，现在默认\(P < Q\)

这个时候每个合法的\(a_i\)都可以直接落到\(Q\)中，因为\(a_{i} \equiv a_{i} \pmod Q\)这样避免了麻烦

然后呢我们发现每次把\((a_{i} + P) \% Q\)会走成一个圈，我们就要求从\(a_{i}\)开始数\(\lfloor \frac{T - 1- a_{i}}{P} \rfloor + 1\)个圈里\(b_{i}\)的总和

这样的话可以断圈为链，复制两份就可以快速查某一段开始走小于圈长步的总和了

这样的圈一共有\(gcd(P,Q)\)个

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define ba 47

#define MAXN 1000005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 +c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

int P,Q,n,m;

int A[MAXN],B[MAXN];

int sum[MAXN * 2],pos[MAXN * 2],tot;

bool vis[MAXN];

int64 ans,T;

int gcd(int a,int b) {

    return b == 0 ? a : gcd(b,a % b);

}

void Solve() {

    read(P);read(Q);read(n);read(m);read(T);

    int x;

    for(int i = 1 ; i <= n ; ++i) {

	read(x);A[x] = 1;

    }

    for(int i = 1 ; i <= m ; ++i) {

	read(x);B[x] = 1;

    }

    if(P > Q) {

	swap(P,Q);

	for(int i = 0 ; i <= 1000000 ; ++i) swap(A[i],B[i]);

    }

    int g = gcd(P,Q);

    for(int i = 0 ; i < g ; ++i) {

	for(int j = 1 ; j <= tot ; ++j) sum[j] = 0;

	tot = 0;

	int x = i;

	while(!vis[x]) {

	    sum[tot + 1] = B[x] + sum[tot];

	    pos[tot + 1] = x;

	    ++tot;

	    vis[x] = 1;

	    x = (x + P) % Q;

	}

	int t = tot;

	for(int j = 1 ; j <= t ; ++j) {

	    if(pos[j] < P && A[pos[j]]) {

		if(T - 1 - pos[j] >= 0) {

		    int64 all = (T - 1 - pos[j]) / P + 1;

		    int64 cnt = all / t;

		    ans += cnt * sum[t];

		    int rem = all % t;

		    if(rem) {

			ans += sum[j + rem - 1] - sum[j - 1];

		    }

		}

	    }

	    sum[tot + 1] = sum[tot] + B[x];++tot;

	    x = (x + P) % Q;

	}

    }

    out(ans);enter;

}

int main(){

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

}