TopCoder SRM 617 Div2 Hard MyVeryLongCake

Div1 Easyを難しくした問題。
http://community.topcoder.com/stat?c=problem_statement&pm=13137

問題

長さNのケーキがある。
ここにNより小さなNの約数の人数の友人が来るので、ケーキを均等に分けたい。
友人が何人でも均等に分けられるように事前にケーキを分割したい。
最少何個に分割しておけばよいか。

解法

Nとの公約数が２以上になるような位置に切れ目を入れればよい。
すなわち答えはN-φ(N)である。(φはオイラーのφ関数）

Div1 EasyはNが小さいので、φ(N)を列挙しても間に合う。
Div2 HardはNが大きいので、φ(N)を列挙する余裕がない。
よって包除定理を使う。ユニークな素因数を奇数または偶数個からなる数の倍数の数を加減算すればよい。

vector<ll> enumdiv(ll n) {
	vector<ll> V;
	if(n==1) return vector<ll>(1,1);
	for(ll i=2;i*i<=n;i++) while(n%i==0) V.push_back(i),n/=i;
	if(n>1) V.push_back(n);
	return V;
}

class MyVeryLongCake {
	public:
	int cut(int n) {
		ll ret=0;
		int i;
		vector<ll> V=enumdiv(n);
		V.erase(unique(V.begin(),V.end()),V.end());
		
		for(int mask=1;mask<1<<V.size();mask++) {
			int mul=(__builtin_popcount(mask)%2)?1:-1;
			ll d=1;
			FOR(i,V.size()) if(mask&(1<<i)) d*=V[i];
			ret+=mul*n/d;
		}
		
		return ret;
	}
};

まとめ

本番問題文の理解が遅れて、だいぶ解くのに時間がかかってしまった…。