【*1900倍数遍历】CF1627 D

朴灿烈づ我的快乐病毒、 2024-03-17 18:17 78阅读 0赞

[Problem - D - Codeforces][]

题意：

![50c011f736a9479c89da9b0b1947a829.png][]

思路：

![9b6895833aab486d8f255675fd726078.jpeg][]

![0b3552c989b94a63b9b455cb5152307f.png][]

**在枚举数列子集的gcd时，通常可以枚举倍数**

对于这道题要注意，j/i的gcd要为1，这样才能保证i是这个子集的最大公约数

Code：

#include <bits/stdc++.h>
     
    //#define int long long
     
    using namespace std;
     
    const int mxn=1e6+10;
    const int mxv=1e6+10;
    const int mxe=2e3+10;
    const int mod=1e9+7;
    const int Inf=0x3f3f3f3f;
    
    int N;
    int a[mxn],mp[mxn];
    
    void solve(){
        cin>>N;
        int mx=-1;
        for(int i=1;i<=N;i++){
            cin>>a[i];
            mp[a[i]]++;
            mx=max(mx,a[i]);
        }
        sort(a+1,a+1+N);
        int ans=0;
        for(int i=1;i<=mx;i++){
            if(mp[i]) continue;
            int res=0;
            for(int j=i*2;j<=1e6;j+=i){
                if(mp[j]) res=__gcd(res,j/i);
            }
            if(res==1) ans++;
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[Problem - D - Codeforces]: https://codeforces.com/contest/1627/problem/D
[50c011f736a9479c89da9b0b1947a829.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/ab3db0d7b3684786910df5107ee1db48.png
[9b6895833aab486d8f255675fd726078.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/4f8e94035baf4f60a3a41ff7c554ee9d.png
[0b3552c989b94a63b9b455cb5152307f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/0830f12f8fd04dfa918b0cba2d12cf6d.png

发表评论取消回复

表情：

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

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

相关阅读

相关 CF1214D

CF1214D 题意： > 给你一个 $ n \\times m $ 的矩阵，求最少用多少个障碍，将 $ (1,1) $ 到 $ (n,m) $ 的路径堵死...

た入场券/ 2024年04月20日 10:34/ 0 赞/ 96 阅读

相关 CF981D

CF981D 题意： > 给你n个数，要求你分成k堆。每堆的内部加和，每堆之间是相与。问最大的值。解法： > 二进制下最大的数的所有位一定是1，所...

缺乏、安全感/ 2024年04月20日 10:26/ 0 赞/ 88 阅读

相关 CF427D

CF427D > SA的奇技淫巧，其实就是板子。题意： > 给定两个字符串，求最短的满足各只出现一次的连续公共字串解析： > 一般情况下，SA...

素颜马尾好姑娘i/ 2024年04月20日 10:25/ 0 赞/ 86 阅读

相关 CF1208D

CF1208D 题意； > 给你一个数组，要求支持单点修改和单点查询解法： > 直接线段树搞一搞就没了。 CODE： includ...

系统管理员/ 2024年04月20日 10:24/ 0 赞/ 96 阅读

相关【枚举倍数+容斥】CF803 F

[Problem - F - Codeforces][] 题意： ![e3f914ba017f4d068fe0f661eb611e23.png][] 思路：正难则反，

╰+哭是因爲堅強的太久メ/ 2024年03月23日 22:41/ 0 赞/ 55 阅读

相关【*1900 图论+枚举思想】CF1328 E

[Problem - E - Codeforces][] 题意： ![5f242b3e379b424cb713c6418d07f247.png][] ![5e58cd37

约定不等于承诺〃/ 2024年03月22日 21:14/ 0 赞/ 83 阅读

相关【*1900倍数遍历】CF1627 D

[Problem - D - Codeforces][] 题意： ![50c011f736a9479c89da9b0b1947a829.png][] 思路： ![9b6

朴灿烈づ我的快乐病毒、/ 2024年03月17日 18:17/ 0 赞/ 79 阅读

相关【*1900 换根DP】CF1092F

感觉很简单，根本没有1900的难度 [CF1092F Tree with Maximum Cost - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)y][CF

怼烎@/ 2024年03月16日 20:12/ 0 赞/ 58 阅读

相关【构造+数论+Tree树上染色】CF1627C

[Problem - 1627C - Codeforces][] 题意：给定一棵树的形态，让你给这棵树的边赋值，使得每对相邻的边的边权和都是质数给树编号那肯定就是染色

淡淡的烟草味﹌/ 2024年03月16日 11:35/ 0 赞/ 58 阅读

相关【*1900 DP+Tree】CF9D

[Problem - 9D - Codeforces][] 题意： ![08c35e73a5d74fb1a152f832fd807c81.png][] 思路：计数问

落日映苍穹つ/ 2024年03月16日 10:29/ 0 赞/ 46 阅读