AtCoder Beginner Contest 170 D - Not Divisible (数学)

题意:有一长度为\(n\)的数组,求该数组中有多少元素不能整除其它任一元素的个数.
题解:刚开始写了个分解质因数(我是傻逼),后来发现直接暴力枚举因子即可,注意某个元素出现多次时肯定不满足情况,再特判数组中存在\(1\)的情况即可.

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <unordered_set>

#include <unordered_map>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

const int INF = 0x3f3f3f3f;

using namespace std;

typedef pair<int,int> PII;

typedef pair<ll,ll> PLL;

int n;

int a[N];

map<int,int> mp;

bool divide(int x){

	int tmp=x;

	for(int i=2;i<=x/i;++i){

		if(x%i==0){

			int t=1;

			while(x%i==0){

				t*=i;

				if(mp[t] && t!=tmp) return false;

				x/=i;

				if(mp[x] && x!=tmp) return false;

			}

			x=tmp;

		}

	}

	return true;

}

int main() {

    ios::sync_with_stdio(false);cin.tie(0);

	cin>>n;

	 for(int i=1;i<=n;++i){

	 	cin>>a[i];

	 	mp[a[i]]++;

	 }

	 int cnt=0;

	 if(mp[1]==1){

	 	cout<<1<<endl;

	 	return 0;

	 }

	 if(mp[1]>1){

	 	cout<<0<<endl;

	 	return 0;

	 }

	 for(int i=1;i<=n;++i){

	 	if(divide(a[i]) && mp[a[i]]==1) cnt++;

	 }

	 cout<<cnt<<endl;

    return 0;

}

巴特西

AtCoder Beginner Contest 170 D - Not Divisible (数学)

最新文章

热门文章