【筛法】ABC170 D - Not Divisible

桃扇骨 2024-03-22 14:35 45阅读 0赞

**太久没写ABC了，不会！**

[D - Not Divisible (atcoder.jp)][D - Not Divisible _atcoder.jp]

题意：

![1b269c7dfa7948a89ecab155d0868d8a.png][]

思路：

特殊点：

ai只有1e6--->值域

考虑在值域中筛倍数，把每一个ai的倍数都筛了

然后当ai被筛的次数只有一个时，满足条件

Code：

#include <bits/stdc++.h>
    
    #define int long long
    #define min(a,b) (a<b?a:b)
    
    using namespace std;
    
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    
    int n;
    int a[mxn],mp[mxn];
    
    void solve(){
    	cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	sort(a+1,a+1+n);
    	for(int i=1;i<=n;i++){
    		for(int j=a[i];j<=a[n];j+=a[i]){
    			mp[j]++;
    		}
    	}
    	int ans=0;
    	for(int i=1;i<=n;i++){
    		if(mp[a[i]]==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;
    }

[D - Not Divisible _atcoder.jp]: https://atcoder.jp/contests/abc170/tasks/abc170_d
[1b269c7dfa7948a89ecab155d0868d8a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/edcd98994f3c49adb862039b251529f8.png

发表评论取消回复

表情：

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

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

相关阅读

相关 Atcoder ABC 139D

Atcoder ABC 139D 解法： > 等差数列求和公式，记得开 $ long long $ CODE: include<iostre...

末蓝、/ 2024年04月20日 10:31/ 0 赞/ 105 阅读

相关【筛法】ABC170 D - Not Divisible

太久没写ABC了，不会！ [D - Not Divisible (atcoder.jp)][D - Not Divisible _atcoder.jp] 题意： ![1b

桃扇骨/ 2024年03月22日 14:35/ 0 赞/ 46 阅读

相关关于欧拉筛法和普通筛法

为的是让一个合数只让最小的一个素数筛去 prime\[\]数组中的素数是递增的,当i能整除prime\[j\]，那么i\prime\[j+1\]这个合数肯定被pri

「爱情、让人受尽委屈。」/ 2024年02月17日 21:36/ 0 赞/ 116 阅读

相关 atcoder abc158 E - Divisible Substring

atcoder abc158 E - Divisible Substring 先看题面 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5n

╰+哭是因爲堅強的太久メ/ 2023年07月12日 11:54/ 0 赞/ 34 阅读

相关【素数判断】埃氏筛法和欧拉筛法（线性筛法）

埃氏筛法埃氏筛法的原理是：给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔

本是古典何须时尚/ 2023年01月10日 10:28/ 0 赞/ 173 阅读

相关质数的筛法

上一篇博客：[LeetCode 1006. 笨阶乘——每日一题][LeetCode 1006.] > 写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Acce

绝地灬酷狼/ 2022年11月15日 15:49/ 0 赞/ 242 阅读

相关素数基本（埃氏筛法/线性筛法）

一、检查n是否为素数最简单思路：所有可能的因数全部试一遍。 int gg(int n) { for(int i=2;i<n;i

拼搏现实的明天。/ 2022年05月17日 06:10/ 0 赞/ 295 阅读

相关筛法求素数

用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时

我不是女神ヾ/ 2022年05月12日 14:42/ 0 赞/ 286 阅读

相关素数筛法

//暴力枚举素数筛法 o(n 根号n) for(int i=2;i<=n;i++){ bool g=0; for(int j=2;jj<

╰+哭是因爲堅強的太久メ/ 2022年04月04日 10:54/ 0 赞/ 288 阅读

相关 1469D - Ceil Divisions （思维）

[题目][Link 1] 思路：首先对于1 2 3 4 . . . 2e5 我想啊，让 i=3 到 2e5-1的数全部 i/2e5 那么这些数就全为1了，1 2 1 1

淩亂°似流年/ 2021年07月16日 16:32/ 0 赞/ 286 阅读