Codeforces #168 Div2 C "k-Multiple Free Set"
問題
k-Multiple Free Setとは、
任意の2つの要素x,y(x<y)において、x*k=yとなるような
要素のペアがない整数の集合である。
n個の整数の集合とkが与えられるので、
ここからk-Multiple Free Setとなるような部分集合を作った時の
最大の要素数を返せ。
制約
1 <= n <= 10^5
1 <= k <= 10^9
1 <= 与えられる整数の集合の値 <= 10^9
考えた事
例えば集合が2,3,4,5,6,7,8,9,10,11,12,13,14,15,16でk=2だとすると
2-4-8-16
3-6-12
5-10
7-14
9
11
13
ってグループになって
例えば2-4-8-16では、最大でも使えるのは2つ
3-6-12では6だけ使って3,12を使えなくするのはまずい
貪欲に小さい数から使ってけば問題なさそう
ソース
int N, K; int main() { cin >> N >> K; set<int> s; // 小さい順のセット map<int,bool> m; // その数字使える? for( int i = 0; i < N; i++ ){ int t; cin >> t; s.insert(t); m[t] = true; } int res = 0; const int MAX_N = 1000000000; int max_d = MAX_N / K; for(set<int>::iterator it = s.begin(); it != s.end(); it++ ){ int n = *it; if( m[n] ){ res++; // n*Kは使えなくする // オーバーフローしないようにif付けといた if( max_d >= n ) m[n*K] = false; } } cout << res << endl; }