Luogu

LOJ

分析

考虑枚举一个 $A_i$ ,那么要求的就是 $\large\sum\limits_{x=0}^{\lfloor\frac{T-1-A_i}{P}\rfloor}\big[(Px+A_i)\mod Q\in B\big]$ 。

可以发现 $(Px+A_i)\mod Q$ 的值会形成一个环,那么我们可以先求出这个环中 $\in B$ 的元素个数的前缀和,那么整个式子的值就可以分完整的环和剩下的元素两部分求了。

然后,注意对于所有到模 $\gcd(P,Q)$ 意义下同余的 $A_i$ ,环内元素是相同的,所以可以放在一起处理。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;

int P,Q,n,m,T,gcd,lcm;
int A[N],B[N],sum[N<<1],pos[N];
bool vis[N];

inline bool cmp(int a,int b) { return a%gcd<b%gcd; }

signed main() {
    P=read(),Q=read(),n=read(),m=read(),T=read()-1;
    for (re int i=1;i<=n;++i) A[i]=read();
    for (re int i=1;i<=m;++i) B[i]=read();
    if (P>Q) swap(P,Q),swap(n,m),swap(A,B);
    
    gcd=__gcd(P,Q),lcm=P/gcd*Q;
    sort(A+1,A+n+1,cmp);
    for (re int i=1;i<=m;++i) vis[B[i]]=1;
    int ans=0;
    for (re int i=0,j=1;i<gcd;++i) {
        int lim=Q/gcd;
        for (re int k=1,l=i;k<=lim;++k,l=(l+P)%Q)
            sum[k]=sum[k+lim]=vis[l],pos[l]=k;
        for (re int k=1;k<=(lim<<1);++k) sum[k]+=sum[k-1];
        while (j<=n&&A[j]%gcd==i) {
            int p=pos[A[j]],len=((T-A[j])%lcm+P)/P;
            ans+=(T-A[j])/lcm*sum[lim]+sum[p+len-1]-sum[p-1];
            ++j;
        }
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 42 PM