• CF986F Oppa Funcan Style Remastered


    CF986F Oppa Funcan Style Remastered 

    不错的图论转化题!

    题目首先转化成:能否用若干个k的非1因数的和=n

    其次,因数太多,由于只是可行性,不妨直接都用质因子来填充!

    即:是否存在ai,使得∑ai*pi=n

    经典套路:同余系最短路!

    最小质因子p0,n一定是若干p0和其他的数凑出来的

    dis[i]表示,%p0=i的数用pi来凑出来,最小是多少。最短路即可。

    如果dis[n%p0]<=n,那么一定可以!

    把询问离线,按照k依次处理。

    一些特殊情况:

    k=1,全都是NO

    k是质数,特判

    k是p1,p2两个质因子,这时最短路点数可能是3e7的,会TLE,于是解不定方程:x*p1+y*p2=n是否有x,y的自然数解。注意很可能爆long long,所以x=(n/g)%(p2/g)*x%(p2/g)

    k有三个以上质因子,点数最多1e5,同余系最短路。

    质因数分解可以暴力分解,线性筛出根号1e15的质数,总分解复杂度<50*4000000

    #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 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('
    ');}
    namespace Modulo{
    const int mod=998244353;
    int ad(int x,int y){return (x+y)>=mod?x+y-mod:x+y;}
    void inc(int &x,int y){x=ad(x,y);}
    int mul(int x,int y){return (ll)x*y%mod;}
    void inc2(int &x,int y){x=mul(x,y);}
    int qm(int x,int y=mod-2){int ret=1;while(y){if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}
    }
    //using namespace Modulo;
    namespace Miracle{
    const int N=1e5+5;
    const int M=31622776+3;
    int m;
    struct qs{
        ll n,k,id;
        bool friend operator <(qs a,qs b){
            return a.k<b.k;
        }
    }q[N];
    int ans[N];
    vector<ll>yin;
    int pri[4000000+5],cnt;
    bool vis[M];
    void sieve(int n){
        for(reg i=2;i<=n;++i){
            if(!vis[i]){
                pri[++cnt]=i;
            }
            for(reg j=1;j<=cnt;++j){
                if(i*pri[j]>n) break;
                vis[i*pri[j]]=1;
                if(i%pri[j]==0) break;
            }
        }
    }
    ll dis[N];
    queue<int>Q;
    void spfa(int mod){
        memset(dis,0x3f,sizeof dis);
        // for(solid y:yin){
        //     // cout<<" yy "<<y<<endl;
        // }
        dis[0]=0;
        Q.push(0);
        while(!Q.empty()){
            int x=Q.front();Q.pop();vis[x]=0;
            // cout<<"xx "<<x<<endl;
            for(reg i=1;i<yin.size();++i){
                int y=(x+yin[i])%mod;
                if(dis[y]>dis[x]+yin[i]){
                    dis[y]=dis[x]+yin[i];
                    if(!vis[y]){
                        vis[y]=1;
                        Q.push(y);
                    }
                }
            }
        }
    }
    void divi(ll K){
        yin.clear();
        ll tmp=K;
        for(reg i=1;(ll)pri[i]*pri[i]<=tmp&&i<=cnt;++i){
            if(tmp%pri[i]==0){
                yin.pb(pri[i]);
                while(tmp%pri[i]==0) tmp/=pri[i];
            }
        }
        if(tmp!=1) yin.pb(tmp);
    }
    ll exgcd(ll a,ll b,ll &x,ll &y){
        if(!b){
            x=1;y=0;return a;
        }
        ll ret=exgcd(b,a%b,y,x);
        y-=(a/b)*x;
        return ret;
    }
    int main(){
        rd(m);
        ll mx=0;
        for(reg i=1;i<=m;++i){
            rd(q[i].n);rd(q[i].k);q[i].id=i;
            mx=max(mx,q[i].k);
        }
        mx=sqrt(mx);
        sieve(mx);
        memset(vis,0,mx+1);
        // prt(vis,0,mx);
        sort(q+1,q+m+1);
        int typ=0;
        for(reg i=1;i<=m;++i){
            if(q[i].k!=q[i-1].k){
                divi(q[i].k);
                typ=0;
                if(q[i].k==1) typ=0;
                else if(yin.size()==1) typ=1;
                else if(yin.size()==2) typ=2;
                else{
                    typ=3;
                    int mod=yin[0];
                    spfa(mod);
                }
            }
            // cout<<" typ "<<typ<<endl;
            // prt(dis,0,yin[0]-1);
            if(typ==0){
                ans[q[i].id]=0;
            }
            else if(typ==1){
                if(q[i].n%yin[0]==0){
                    ans[q[i].id]=1;
                }
            }else if(typ==2){
                // cout<<" typ==2 "<<endl;
                ll x,y;
                ll g=exgcd(yin[0],yin[1],x,y);
                // cout<<" gg "<<g<<" "<<yin[0]<<" "<<yin[1]<<endl;
                // cout<<"st "<<x<<" "<<y<<" : "<<x*yin[0]+y*yin[1]<<endl;
                ll md=yin[1]/g;
                x=(x%md+md)%md;
                if(q[i].n%g==0){
                    x=(q[i].n/g)%md*x%md;
                    y=(q[i].n-x*yin[0])/yin[1];
                    // cout<<" x "<<x<<" y "<<y<<endl;
                    // cout<<" eql "<<x*yin[0]+y*yin[1]<<endl;
                    if(y>=0){
                        ans[q[i].id]=1;
                    }
                }
            }else{
                if(dis[q[i].n%yin[0]]<=q[i].n){
                    ans[q[i].id]=1;
                }
            }
        }
        for(reg i=1;i<=m;++i){
            if(ans[i]) puts("YES");
            else puts("NO");
        }
        return 0;
    }
    
    }
    signed main(){
        Miracle::main();
        return 0;
    }
    
    /*
       Author: *Miracle*
    */

     PS:

    以后解一个多元一次不定方程,最小的数不太大的时候,同余最短路都可以尝试!

  • 相关阅读:
    A Survey of Machine Learning Techniques Applied to Software Defined Networking (SDN): Research Issues and Challenges
    A Deep Learning Based DDoS Detection System in Software-Defined Networking (SDN)
    解决win10 USB转串口无法使用
    Feeder-Link Outage Prediction Algorithms for SDN-based High-Throughput Satellite
    Flow monitoring in Software-Defined Networks
    Refining Network Intents for Self-Driving Networks
    2020生活变化
    【转载】 图解最小堆形成-以数组方式表示
    福大软工 · 最终作业
    福大软工 · 第十二次作业
  • 原文地址:https://www.cnblogs.com/Miracevin/p/10955893.html
一二三 - 开发者的网上家园