首页 > 其他分享 >【2022杭电多校】第九场 1008 Shortest Path in GCD Graph 【容斥+优化】

【2022杭电多校】第九场 1008 Shortest Path in GCD Graph 【容斥+优化】

时间:2022-08-17 01:12:37浏览次数:97  
标签:杭电多校 gcd int Graph base mp cntp define GCD

链接

https://acm.hdu.edu.cn/showproblem.php?pid=7240

题意是有n个点组成的完全图,每个点的权重组成了1-n的排列,点i和点j的距离为\(gcd(i,j)\) ,给出q组询问,每次询问给出u点和v点,你需要回答u和v的最短距离和最短路的条数

思路

如果\(gcd(u,v)==1\),答案为 1 1
否则最短路的长度一定为2,因为一定可以找到一个点x(至少可以找到1)满足\(gcd(u,x)==1\), \(gcd(x,v)==1\),最短路的条数即为与u和v都互质的点数
如果\(gcd(u,v)==2\),也可以直接从u走到v,那么答案另外还要+1

由分析知,如果我们可以找到u和v的所有质因子,那么根据容斥原理,我们就可以求出1-n范围内和 u或v gcd>1的数的数量
而因为n<=1e7,u中最多有2、3、5、7、11、13、17、19,8个不同质因子,最少有23、29、31、37,4个不同质因子,所以u和v总共最多包含12个质因子

这个数据范围可以考虑枚举所有状态.具体地:

(注意必须需要使用单次询问2^12的写法,否则会tle)

做法1

枚举12个数每个数是否出现的状态,枚举出状态之后,再遍历这个状态,求出答案

如果直接枚举,时间复杂度是 12 * 2 ^ 12,会超时,因此把枚举每一位换成减去当前状态的lowbit

我这样做还是t,再存储每次询问的{u,v}二元组,如果重复问到直接回答即可ac

点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pb push_back
using namespace std;
const int N = 1e7+10, mod = 998244353;
int t, n, q, u, v, g;
int prime[22], cntp;
bool vis[N];
int cnt,p[N],log_[N];
int mp[N];
int ans;
map<pii,int>visit;

void init(int N){
    cnt=0;
    for(int i=2;i<=N;i++){
        if(!vis[i]) p[++cnt]=i;
        for(int j=1;j<=cnt&&i*p[j]<=N;j++){
            vis[i*p[j]]=1;
            if(i%p[j]==0){
                break;    
            }
        }
    }
}

void func(int x){
    if(!vis[x]){
        if(mp[x]==0){
            mp[x]=1;
            prime[cntp++]=x;
        }
        return;
    }
    for(int i=1;i<=cnt;i++){
        if(x<p[i]) break;
        if(x%p[i]==0){
            if(mp[p[i]]==0){
                mp[p[i]]=1;
                prime[cntp++]=p[i];
            }
            while(x%p[i]==0) x/=p[i];
        }
    }
    if(x>1){
        if(mp[x]==0){
            mp[x]=1;
            prime[cntp++]=x;
        }
    }
}

inline int lowbit(int x){
    return x&-x;
}

void solve(){
    ans = 0;
    for(int S = 1;S < (1 << cntp); S++){
        int sum = 0;
        ll base = 1;
        int SS = S;
        while(SS){
            int now = lowbit(SS);
            sum++;
            base *= prime[log_[now]];
            SS -= now;
        }
        if(sum & 1) ans += n/base;
        else ans -= n/base;
        // cout<<S<<' '<<base<<' '<<n/base<<endl; ///
    }
}

int main(){
    init(1e7);
    scanf("%d%d",&n,&q);
    for(int i=0;i<12;i++) log_[(1<<i)] = i;
    while(q--){
        scanf("%d%d",&u,&v);
        if(u > v) swap(u,v);
        g = __gcd(u,v);
        if(g == 1){
            puts("1 1");
            continue;
        }
        printf("2 ");
        if(visit[{u,v}]){
            printf("%d\n",visit[{u,v}]);
            continue;
        }
        cntp = 0;
        func(u); func(v);
        // cout<<cntp<<endl; 
        solve();
        ll tem = n - ans;
        if(g == 2) tem += 1;
        printf("%lld\n",tem);
        visit[{u,v}]=tem;
        for(int i=0;i<=cntp;i++) mp[prime[i]]=0;
    }
    system("pause");
    return 0;
}

做法2:dfs

直接dfs就可以做到 2 ^ 12的复杂度,因为一位一位访问的同时就存储了结果,不需要再次遍历当前状态了

点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pb push_back
using namespace std;
const int N = 1e7+10, mod = 998244353;
int t, n, q, u, v, g;
int prime[22], cntp;
bool vis[N];
int cnt,p[N],log_[N];
int mp[N];
int ans;

void init(int N){
    cnt=0;
    for(int i=2;i<=N;i++){
        if(!vis[i]) p[++cnt]=i;
        for(int j=1;j<=cnt&&i*p[j]<=N;j++){
            vis[i*p[j]]=1;
            if(i%p[j]==0){
                break;    
            }
        }
    }
}

void func(int x){
    if(!vis[x]){
        if(mp[x]==0){
            mp[x]=1;
            prime[cntp++]=x;
        }
        return;
    }
    for(int i=1;i<=cnt;i++){
        if(x<p[i]) break;
        if(x%p[i]==0){
            if(mp[p[i]]==0){
                mp[p[i]]=1;
                prime[cntp++]=p[i];
            }
            while(x%p[i]==0) x/=p[i];
        }
    }
    if(x>1){
        if(mp[x]==0){
            mp[x]=1;
            prime[cntp++]=x;
        }
    }
}

void dfs(int now,int sum,ll base){
    if(now == cntp){
        // if(base == 1) return;
        if(sum & 1) ans -= n/base;
        else ans += n/base;
        return;
    }
    dfs(now+1,sum,base);
    dfs(now+1,sum+1,base*prime[now]);
}

int main(){
    init(1e7);
    scanf("%d%d",&n,&q);
    for(int i=0;i<12;i++) log_[(1<<i)] = i;
    while(q--){
        scanf("%d%d",&u,&v);
        g = __gcd(u,v);
        if(g == 1){
            puts("1 1");
            continue;
        }
        printf("2 ");
        cntp = 0;
        func(u); func(v);
        // solve();
        ans = 0;
        dfs(0,0,1);
        // ll tem = n - ans;
        ll tem = ans;
        if(g == 2) tem += 1;
        printf("%lld\n",tem);
        for(int i=0;i<=cntp;i++) mp[prime[i]]=0;
    }
    system("pause");
    return 0;
}

标签:杭电多校,gcd,int,Graph,base,mp,cntp,define,GCD
From: https://www.cnblogs.com/re0acm/p/16593522.html

相关文章

  • pip install Appium-Python-Client 报Failed to build cryptography错误解决办法
    使用Pthon编写自动化脚本时,导入appium失败,百度查到需要安装Appium-Python-Client,于是CMD执行pipinstallAppium-Python-Client,报错:Buildingwheelsforcollectedpacka......
  • graphql .net
    安装GraphQL7.0.0GraphQL.SystemTextJson7.0.0HelloWorldpublicclassProgram{publicstaticasyncTaskMain(string[]args){......
  • 2022杭电多校第八场1、7、5
    1001Theramore观察以下两种情况:以0为例,上图就是说,只要有两个连续的0,我们就可以一直把它们往前移动直到移动到首位。同理只要有两个连续的1我们就可以把它们移动到尾部......
  • 开源图编辑库 NebulaGraph VEditor 的设计思路分享
    本文首发于NebulaGraph公众号NebulaGraphVEditor是一个拥有高性能、高可定制的所见即所得图可视化编辑器前端库。NebulaGraphVEditor底层基于SVG绘图,它通过合......
  • CF986C AND Graph(图论+二进制连边)
    CF986CANDGraph\(\color{yellow}{\bigstar\texttt{Hint}}\):和每个点连接的点是这个数取反后的子集,考虑将这个点和它的反连边,那么所有对应的数的子集都是同一个连通块内......
  • 杭电多校杂题收录
    前言和学长学弟一起打的hdu多校,打的很菜没啥难题收录,因为难的我都不会做。正题hdu7152-Copy题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=7152题目大意\(n......
  • [WATER]玩了一下 Graph Editor
    GraphEditor稳定的六边形无论多么扭曲,边长设小后基本总会猛烈跳动后保持平衡。123456789101112131415161718192021222324252627282930......
  • 2022 杭电多校第八场 Vale of Eternal 凸包+找规律
    主要是存个代码,还有我踩的坑。。cin和cout真的很慢,很慢,非常慢..还有就是先把凸包求出来了,然后才能考虑凸包面积啥的刚开始思路错了,直接上多边形面积明明输出和标程都一......