問題概要
相異なる整数の集合が与えられる。この集合に対し、以下の処理を繰り返し適用する。
- a > b なる二つの要素を選び、a を b で整数除算した値が集合に含まれなければ、これを集合に加える
それ以上操作を適用できなくなったときの、集合の要素数を求めよ。
解法
集合に含まれる最大の値を N と表記します。
集合に新たな要素を加えるとき、加えられる値は明らかに N より小さくなります。鳩ノ巣原理より、N より大きい回数の操作を適用することはできません。a, b の選び方を全て試したとしても操作一回あたり であり、全体では となるので、与えられた手順をそのまま実装することで解くことができます。
コード
#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define FOR( v, c ) for ( auto &v : c ) #define ALL( c ) (c).begin(), (c).end() class DivideByZero { public: int CountNumbers( vector <int> numbers ) { vector<bool> cur( 101 ), next; FOR( n, numbers ) { cur[n] = true; } do { next = cur; REP( a, 1, 101 ) { REP( b, 1, a ) { if ( cur[a] && cur[b] && !next[ a / b ] ) { next[ a / b ] = true; } } } swap( cur, next ); } while ( cur != next ); return count( ALL( cur ), true ); } };