[SNOI2019]数论

野性酷女 2022-01-12 10:51 192阅读 0赞

其实题目并不难。。。

入手想法：

枚举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
    */

挺套路的其实。。。

转载于:https://www.cnblogs.com/Miracevin/p/10853746.html