P1978 题解

sto_yyrdxh_orz · 2022-07-31 11:34:17 · 个人记录

题目大意：

第一行输入两个数 n 和 k ，接下来一行 n 个数，表示集合 a 里的元素，不能让答案集合 s 里的任意元素 x*k 在答案集合里出现，输出答案集合的元素个数。

思路：

咱们先分析一下数据范围

虽然从这里咱们发现 long long 是完全可以存下 2^{63}-1 的，但是题目要求不能出现 x*k 的元素， 10^5 乘 2^{63}-1 明显爆 long long 了，所以咱们得换一种思路。

大家都知道a*b=c 可以写成 c÷a=b 。

所以，咱们可以换一种思路，把乘法转换为除法。

首先，咱们先将集合 a 的元素按照从小到大排好序，每次判断一下当前元素取余 k 是否不等于 0 ，如果不等于 0 ，我们就可以把这个元素放入集合里，还有一种情况就是当前元素取余 k 等于 0 并且这个元素没有出现在答案集合里，我们也可以把这个元素放入集合里。

提示：

• 答案集合可以用 set ，判断是否存在的时候直接用 s.count(当前元素的变量名就行) 。
• 如果不了解 set 的可以点这里。

具体代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+7;
long long n, m, a[N];
set<long long> s;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1, a+1+n);
    for(int i=1;i<=n;i++){
        if((a[i]%m==0&&s.count(a[i]/m)==0)||a[i]%m!=0){
            s.insert(a[i]);
        }
    }
    cout<<s.size();
    return 0;
}