SRM 510 D2L3：TheLuckyBasesDivTwo，brute force，optimization

题目：http://apps.topcoder.com/wiki/display/tc/SRM+510

若直接用brute force则时间复杂度为 O(n)，但当base 取 √n时，在√n进制下n的位数最多为2，所以可以brute force至√n，时间复杂度为O(√n)，base > √n时，可以由其最终表示的数来倒退base，a + b * base  = n，a，b可为4或7，计算base是否符合条件。

代码：

#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <iostream>
#include <sstream>
#include <iomanip>

#include <bitset>
#include <string>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
using namespace std;

#define CHECKTIME() printf("%.2lf\n", (double)clock() / CLOCKS_PER_SEC)
typedef pair<int, int> pii;
typedef long long llong;
typedef pair<llong, llong> pll;
#define mkp make_pair

/*************** Program Begin **********************/

class TheLuckyBasesDivTwo {
public:
	bool isLucky(long long n, long long base)
	{
		while (n) {
			long long t = n % base;
			n /= base;
			if (t != 4 && t != 7) {
				return false;
			}
		}
		return true;
	}
	long long find(long long n) {
		long long res = 0;
		if (4 == n || 7 == n) {
			return -1;
		}
		int lim = floor(sqrt(n * 1.0 + 0.5));
		for (int i = 2; i <= lim; i++) {
			if (isLucky(n, i)) {
				++res;
			}
		}
		int L[] = {4, 7};
		int R[] = {4, 7};
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				if ( (n - L[i]) % R[j] == 0 ) {
					long long base = (n - L[i]) / R[j];
					if (base > lim) {
						++res;
					}
				}
			}
		}
		return res;
	}

};

/************** Program End ************************/

SRM 510 D2L3：TheLuckyBasesDivTwo，brute force，optimization,布布扣,bubuko.com

SRM 510 D2L3：TheLuckyBasesDivTwo，brute force，optimization

原文：http://blog.csdn.net/xzz_hust/article/details/20575241