HDU1695GCD 容斥

Love The Way You Lie 2022-05-16 02:55 224阅读 0赞

原来用莫比乌斯写过这个[传送门][Link 1]，发现这个用容斥挺好理解，就是跑的比莫比乌斯慢，莫比乌斯跑了40ms，这个跑了400ms。

估计复杂度是O(n\*6\*2^6)大约4e7。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=1e5+10;
    vector<int> p[N];
    
    void getP(){
        for(int i=2; i<=1e5; i++){
            int m=sqrt(i+0.5), t=i;
            for(int j=2; j<=m; j++) if(t%j==0){
            p[i].push_back(j);      while(t%j==0) t/=j; }
    
            if(t>1) p[i].push_back(t);
        }
    }
    
    ll cal(int id, int s, int n){
        ll v=1, cnt=0;
        for(int i=0; i<p[id].size(); i++){
            if((1<<i)&s){
                cnt++; v*=p[id][i];
            }
        }
    
        v=n/v;
        if(cnt&1) return v;
        else return -v;
    }
    
    int main(){
        getP();
    
        int T, cas=0;
        scanf("%d", &T);
        while(T--){
            int a, b, c, d, k;
            scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
    
            if(k==0){
                printf("Case %d: 0\n", ++cas);
                continue;
            }
    
            b/=k; d/=k;
            if(b>d) swap(b,d);
            ll ans=0;
            for(int i=1; i<=d; i++){
                int t=min(i, b);
                ans+=t;
                for(int j=1; j<1<<(p[i].size()); j++)
                    ans-=cal(i, j, t);
    
            }
            printf("Case %d: %lld\n", ++cas, ans);
        }
        return 0;
    }

[Link 1]: https://blog.csdn.net/du_lun/article/details/81672816

发表评论取消回复

表情：

评论列表（有 0 条评论，224人围观）

还没有评论，来说两句吧...

相关阅读

相关 hdu1695（容斥原理）

求（1，b）区间和（1，d）区间里面gcd(x, y) = k的数的对数（1<=x<=b , 1<= y <= d）。 b和d分别除以k之后的区间里面，只需要求gcd(x,

一时失言乱红尘/ 2024年02月17日 23:41/ 0 赞/ 45 阅读

相关 Hdu 1695 GCD (数论容斥原理)

参考了：[HDU 1695 GCD 【数论，容斥原理】 - 脑残 - 博客频道 - CSDN.NET][HDU 1695 GCD _ - _ - _ - CSDN.NET]

落日映苍穹つ/ 2022年08月26日 08:10/ 0 赞/ 145 阅读

相关 Hdu 4451 Dressing (简单容斥)

题意：有N种衣服，M种裤子和K种鞋子，已知哪些衣服和哪些裤子不能搭配，哪些裤子和哪些鞋子不能搭配，现在要选择一套(衣服+裤子+鞋子)，问有多少种搭配方法。思路：所有的不和谐

逃离我推掉我的手/ 2022年08月26日 08:04/ 0 赞/ 127 阅读

相关 hdu 1695 GCD (欧拉函数+容斥原理+素因子分解)

hdu 1695 GCD (欧拉函数+容斥原理+素因子分解) ：[http://acm.hdu.edu.cn/showproblem.php?pid=1695][http_ac

绝地灬酷狼/ 2022年07月25日 15:58/ 0 赞/ 160 阅读

相关 HDU 1695 GCD （容斥原理）

[HDU 1695][] 题意：求有多少对(x,y), (1<=x<=b,1<=y<=d), 满足gcd(x,y)=k。题解：注意到gcd(x,y)=k,说明x,y

男娘i/ 2022年07月12日 09:55/ 0 赞/ 225 阅读

相关 HDU 2197 本原串（数学+容斥）

题目链接： [HDU 2197][] 题意：由0和1组成的串中，不能表示为由几个相同的较小的串连接成的串，称为本原串，有多少个长为n（n<=100000000)的本

朱雀/ 2022年06月15日 12:07/ 0 赞/ 174 阅读

相关 hdu 1695(欧拉公式，容斥原理||莫比乌斯反演)

GCD

古城微笑少年丶/ 2022年06月10日 07:42/ 0 赞/ 153 阅读

相关 HDU 6397 Character Encoding（容斥）

[传送门][Link 1] 挑选m个数，和为k，数的取值为0~n-1，相当于将每个数加1，使挑的m个数和是k+m，可以看成k+m个1，用m-1个隔板，隔成m分，所以总数为C

╰半橙微兮°/ 2022年05月16日 04:36/ 0 赞/ 154 阅读

相关 HDU1695GCD 容斥

原来用莫比乌斯写过这个[传送门][Link 1]，发现这个用容斥挺好理解，就是跑的比莫比乌斯慢，莫比乌斯跑了40ms，这个跑了400ms。估计复杂度是O(n\6\2^6)大

Love The Way You Lie/ 2022年05月16日 02:55/ 0 赞/ 225 阅读

相关 HDU 5514 巧妙的容斥

题意：给你一些数，对于每一个数a，可以得到t=(t+a)%m,t可以无限制算下去，问0~m-1之间能被得到的数的和。思路：根据欧几里得原理，a能得到的数就是a和m的最大公约

迈不过友情╰/ 2022年05月08日 08:36/ 0 赞/ 172 阅读