Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

罗马数字规则：参考wiki：http://zh.wikipedia.org/wiki/%E7%BD%97%E9%A9%AC%E6%95%B0%E5%AD%97
1， 罗马数字共有7个，即I（1）、V（5）、X（10）、L（50）、C（100）、D（500）和M（1000）。

罗马数字中没有“0”。
2， 重复次数：一个罗马数字最多重复3次。
3， 右加左减：
在较大的罗马数字的右边记上较小的罗马数字，表示大数字加小数字。
在较大的罗马数字的左边记上较小的罗马数字，表示大数字减小数字。
4， 左减的数字有限制，仅限于I、X、C，且放在大数的左边只能用一个。
(*) V 和 X 左边的小数字只能用Ⅰ。
　 (*) L 和 C 左边的小数字只能用X。
　　 (*) D 和 M 左 边的小数字只能用C。

// LeetCode, Integer to Roman
// 时间复杂度 O(num),空间复杂度 O(1) 
class Solution{
public:
	string intToRoman(int num) {
		const int radix[] = { 1000, 900, 500, 400, 100, 90,
			50, 40, 10, 9, 5, 4, 1 };
		const string symbol[] = { "M", "CM", "D", "CD", "C", "XC",
			"L", "XL", "X", "IX", "V", "IV", "I" };
		string roman;
		for (size_t i = 0; num > 0; ++i)
		{
			int count = num / radix[i];
			num %= radix[i];
			for (; count > 0; --count) roman += symbol[i];
		}
		return roman;
	}
};