torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder, SRM 617, Division 2, Level 3 : MyVeryLongCake

問題概要

Division 1, Level 1 と制約以外同一)

 長さが n の細長いケーキがある。このケーキを予めいくつかの切片に切り分けておき、訪ねてきた友達に振る舞いたい。ケーキの分配は次のように行う
ケーキの端から、連続する複数の切片を一人目の友達に振る舞う。以降全ての友人にも同じように処理する。
 訪ねてくる友達の正確な人数は分からないが、n 未満かつ n を割り切る人数であることが分かっている。全ての友達に同じ量のケーキを分配できるようにしておきたいとき、最小でいくつの切片に分割しておけばよいか、求めよ。


解法(メビウス関数)

 まず、valid な分配が可能となる必要十分条件は何かを考えます。題意より、分配は任意の n の約数 d について、dk ( k = 1, 2, 3 ... x / d - 1 ) の位置で分割できる(=この位置に切れ込みがある)ことを要請します。これ以外の位置に切れ込みを入れてもそこで分割されることはないので、これが必要十分条件です。従って、n の約数の倍数からなる集合の要素数が分かればそれが切れ込みの数となります。ここまで分かれば、問題の答えは (切れ込みの数) + 1 として求まります。しかし、約数の列挙は O( \sqrt n ) でできますが(素数判定法と同じ感じで)、そのままやるとある二つの数の公倍数を重複して数えてしまうためうまく行きません。
 ここで包除原理の考え方を使います。ある整数 a の倍数からなる集合を m( a ) と書きます。ある二つの整数 p, q に関して、pq の倍数からなる集合は、m( p ) ∩ m( q ) です。三つ以上の整数の積の倍数に関しても同じことが言えます。包除原理を適用するためには、符号を決定するためにいくつの集合の積集合なのかを決定できる必要がありますが、これはいくつの数に素因数分解できるかと同値です。また、ある n の約数 d の倍数であって、n 未満であるものの個数は n / d - 1 です。
 これで必要な要素の求め方が分かりましたが、一つ例外があります。n の約数を小さい方から順に見ていくとすると、ある時点で着目している n の約数 d が平方因子をもつとき、d の倍数からなる集合は以前に数え上げられています。従ってこの場合の d は無視する必要があります。
 以上をまとめると、各 n の倍数 d について、約数からなる集合の要素数 n / d - 1 に次のような係数が付きます。

  • 0 ( n が平方因子をもつとき)
    1. 1 ( n が平方因子をもたず、奇数個の素因数に分解されるとき)
    • 1 ( n が平方因子をもたず、偶数個の素因数に分解されるとき)

これはメビウス関数の符号反転になっています。従って、全ての n の約数 d について、-μ( d ) * ( n / d - 1 ) の総和をとって、最後に 1 を加えたものが問題の答えです。

解法(φ関数)

 「n の約数の倍数」は「 n と互いに素ではない数」と同値なので、求めるものは n - ( n と互いに素な整数の数) とも書けます。オイラーのφ関数はまさに n と互いに素な整数の数を求める関数なので、問題の答えは n - φ( n ) と書けます。

コード(メビウス関数)

using LL = long long;
using VI = vector<int>;

#define FOR( e, c ) for ( auto &e : c )
#define PB( n ) push_back( n )

// メビウス関数
// n が 1 でない平方数で割り切れるとき、0
// そうでないとき、n の約数の個数を k として ( -1 ) ^ k
map<int,int> mobius( int n );

class MyVeryLongCake
{
public:
	int cut(int n)
	{
		auto mob_res = mobius( n );
		LL res = 0;

		for ( LL a = 2; a * a <= n; a++ )
		{
			if ( n % a )
			{
				continue;
			}

			const LL b = n / a;

			VI ds( 1, a );
			if ( a != b )
			{
				ds.PB( b );
			}

			FOR( d, ds )
			{
				res += -mob_res[d] * ( n / d - 1 );
			}
		}

		return res + 1;
	}
}

コード(φ関数)

// euler の φ 関数
// n 以下の、n と互いに素な整数の数を求める
// x^φ(m) ≡ 1 ( mod m )
long long euler_phi( long long n );

class MyVeryLongCake
{
public:
	int cut(int n)
	{
		return n - euler_phi( n );
	}
};