正解:数论

解题报告:

,,,这题还蛮妙的$QwQ$(,,,其实所有数论题对我来说都挺妙的$kk$然后我真的好呆昂我理解了好久$QAQ$

考虑先建$Q$个点,编号为$[0,Q)$,表示膜$Q$的余数.然后每个点$i$向$(i+P)\ mod Q$连边$QwQ$

显然这个是会成环的,事实上这个环的长度就$\frac{P\cdot Q}{gcd(P,Q)}$(不明白的可以去康那道很古早的考过好几遍了的跑跑步那题?那题不是证了个结论是说.在膜$Q$意义下每次走$P$,只会有$gcd(P,Q)$个环嘛,放到这题里就是有$gcd(P,Q)$个长度为$\frac{P\cdot Q}{gcd(P,Q)}$的环$QwQ$

然后枚举膜$P$的余数$a_i$,显然顺着边跑就等同于$a_i$不变,然后现在就变成,从$a_i$开始在环中跑$\lfloor\frac{T-1-a_i}{P}\rfloor$步,问有多少步是跑到的编号膜$Q\in B$的点上$QwQ$

所以考虑先预处理一个环中的属于$B$的数的数量,然后最后剩下的一点小尾巴特殊算下就欧克

$over$!

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define il inline

#define rg register

#define gc getchar()

#define int long long

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(rg int i=x;i<=y;++i)

#define my(i,x,y) for(rg int i=x;i>=y;--i)

#define ub(i,x) upper_bound(G[i].begin(),G[i].end(),x)-G[i].begin()

const int N=1e6+;

int P,Q,n,m,T,d,len,a[N],id[N],as;

bool b[N];

vector<int>G[N];

il int read()

{

    rg char ch=gc;rg int x=;rg bool y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

int gcd(ri x,ri y){return y?gcd(y,x%y):x;}

signed main()

{

    P=read();Q=read();n=read();m=read();T=read()-;rp(i,,n)a[i]=read();rp(i,,m)b[read()]=;d=gcd(P,Q);len=P*Q/d;

    rp(i,,d-){ri cnt=,nw=i;while(!cnt || nw!=i){id[nw]=++cnt;if(b[nw])G[i].push_back(cnt);nw=(nw+P)%Q;}}

    rp(i,,n)

    {

        ri num=(T-a[i])/len,to=(T-num*len-a[i])/P;as+=num*(int)(G[a[i]%d].size());

        ri l=id[a[i]],r=id[(to*P+a[i])%Q];

        if(l<=r){as-=ub(a[i]%d,l-);as+=ub(a[i]%d,r);}

        else{swap(l,r);as+=(int)(G[a[i]%d].size());++l;--r;if(l>r)continue;as+=ub(a[i]%d,l-);as-=ub(a[i]%d,r);}

    }

    printf("%lld\n",as);

    return ;

}

巴特西

洛谷$P5330\ [SNOI2019]$数论数论

正解:数论

解题报告:

最新文章

热门文章

巴特西

洛谷$P5330\ [SNOI2019]$数论 数论

正解:数论

解题报告:

最新文章

热门文章

洛谷$P5330\ [SNOI2019]$数论数论