其实题目并不难...
入手想法:
枚举 x, 不行
枚举 a,b 考虑贡献, 不行
(然后就不会了)
其实, 枚举 a, 考虑可以贡献的 b,,,,
对 b 开桶, 枚举 a,a+k*p mod q 有没有.(其实粗略想到了这里,,,)
有循环节!
然后是一个环,
枚举 0~Q-1,+p 连边
一共有 gcd(p,q) 个环,
直接考虑循环多少次 (循环节走的长度是 lcm(p,q))
边角余料处理即可.....
注意:
如果 p>q 最好 swap(p,q), 方便
同时 swap(n,m),swap(a,b)
- #include<bits/stdc++.h>
- #define reg register int
- #define il inline
- #define fi first
- #define se second
- #define mk(a,b) make_pair(a,b)
- #define numb (ch^'0')
- #define pb push_back
- #define solid const auto &
- #define enter cout<<endl
- #define int long long
- #define pii pair<int,int>
- using namespace std;
- typedef long long ll;
- template<class T>il void rd(T &x){
- char ch;x=0;bool fl=false;
- while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
- for(x=numb;isdigit(ch=getchar());x=x*10+numb);
- (fl==true)&&(x=-x);
- }
- template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');}
- template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
- template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
- namespace Miracle{
- const int N=1e6+5;
- int p,q,n,m;
- ll T;
- int id[N],be[N],sum[N];
- int num[N],all[N];
- int a[N],b[N],buc[N];
- int cnt;
- ll lcm;
- vector<int>mem[N];
- ll calc(int a){
- // cout<<"calc"<<a<<endl;
- if(T<a) return 0;
- ll turn=(T-a)/lcm;
- ll ret=buc[a];
- ret+=(ll)all[be[a]]*turn;
- int rm=(T-a-turn*lcm)/p;
- if(id[a]+rm>num[be[a]]){
- ll lp=all[be[a]]-sum[a]+sum[mem[be[a]][(id[a]+rm)%num[be[a]]]];
- ret+=lp;
- }else{
- ll lp=sum[mem[be[a]][id[a]+rm]]-sum[a];
- ret+=lp;
- }
- // cout<<"ret"<<ret<<endl;
- return ret;
- }
- int nxt(int x){
- return (x+p)%q;
- }
- int main(){
- rd(p);rd(q);rd(n);rd(m);rd(T);
- --T;
- for(reg i=1;i<=n;++i) rd(a[i]);
- for(reg i=1;i<=m;++i) rd(b[i]);
- if(p>q){
- swap(n,m);swap(a,b);swap(p,q);
- }
- for(reg i=1;i<=m;++i) buc[b[i]]=1;
- for(reg i=0;i<q;++i){
- if(be[i]) continue;
- int now=i;
- ++cnt;be[i]=cnt;
- sum[i]=buc[i];
- id[i]=++num[cnt];
- mem[cnt].push_back(233);
- mem[cnt].push_back((int)i);
- now=nxt(now);
- int las=i;
- while(now!=i){
- mem[cnt].push_back(now);
- be[now]=cnt;
- sum[now]=sum[las]+buc[now];
- id[now]=++num[cnt];
- las=now;now=nxt(now);
- }
- all[cnt]=sum[las];
- }
- ll ans=0;
- lcm=p/__gcd(p,q)*q;
- for(reg i=1;i<=n;++i){
- ans+=calc(a[i]);
- }
- ot(ans);
- return 0;
- }
- }
- signed main(){
- Miracle::main();
- return 0;
- }
- /*
- Author: *Miracle*
- Date: 2019/5/12 20:24:41
- */
挺套路的其实...
[SNOI2019] 数论
来源: http://www.bubuko.com/infodetail-3056551.html