TopCoder Open 2014, Algorithm, Round 1C, Level 2 : FizzBuzzTurbo

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13062&rd=15958

問題概要

　正整数 A, B が与えられる。区間 [ A, B ] での FizzBuzz に於いて、"Fizz", "Buzz", "FizzBuzz" のそれぞれが発話される回数を求めよ。
　ただし、1 ≦ A ≦ B ≦ 10^18 である。

解法

　区間 [ A, B ] について求めるタイプの問題では、[ 0, N ] について求めることができれば、[ A, B ] の場合を [ 0, B ] から [ 0, A ) の場合を引くことで求めることができます。この問題でもそうします。
　[ 0, N ] の場合ですが、集合 a, b, c を考えて、a = N 以下の 3 の倍数、b = N 以下の 5 の倍数、c = N 以下の 15 の倍数　とします。また、c = a ∩ b です。このとき、"FizzBuzz" の回数は |c| です。また、"Fizz" の回数は "Fizz" を含む発話から "FizzBuzz" を除いたものなので、| a ＼ c | です。"Buzz" についても同様にして、| b ＼ c | です。a, b, c の要素数はそれぞれ N / 3 , N / 5, N / 15 と求まるので、差集合の要素数も適当に計算することができます。
　あとは、B までの結果から A - 1 までの結果を引けば問題の答えが得られます。

コード

using LL = long long;
template < typename T = int > using VT = vector<T>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class FizzBuzzTurbo
{
public:
	vector<long long> counts( long long A, long long B )
	{
		const VT<LL> a = solve( A - 1 );
		const VT<LL> b = solve( B );

		VT<LL> res( 3 );
		REP( i, 0, 3 )
		{
			res[i] = b[i] - a[i];
		}
		return res;
	}

	VT<LL> solve( const LL N )
	{
		const LL a = N / 3;
		const LL b = N / 5;
		const LL c = N / 15;

		return VT<LL>( { a - c, b - c, c } );
	}
};