HDU 4937 Lucky Number(數論)

HDU 4937 Lucky Number

題目鏈接

題意：給定一個數字，求它再x進制下，每位進制位上都只有3，4，5，6，求這樣的x有多少種，如果無限種輸出-1

思路：首先3 4 5 6特判掉是無限的，很容易想到就不證明了，然後就是枚舉數字的最後一位3，4，5，6，然後進制數肯定來自這個數字的因子，因為剩下的數字肯定是a1x^1 + a2x^2 + a3x^3...這樣的，這樣只要在因子中找進制，去判斷即可。找因子的方法用先分解再dfs找，直接試除會超時

代碼：

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long ll;
const ll N = 1e6 + 5;

int t, vis[N], pn = 0, cnt[N], fn;
ll n, prime[N], fra[N];
set ans;

void getFra(ll n) {
    fn = 0;
    for (int i = 0; i < pn && n >= prime[i]; i++) {
	if (n % prime[i] == 0) {
	    fra[fn] = prime[i];
	    cnt[fn] = 0;
	    while (n % prime[i] == 0) {
		n /= prime[i];
		cnt[fn]++;
	    }
	    fn++;
	}
    }
    if (n != 1) {
	fra[fn] = n;
	cnt[fn++] = 1;
    }
}

bool check(ll b) {
    ll tmp = n;
    while (tmp) {
	if (tmp % b < 3 || tmp % b > 6)
	    return false;
	tmp /= b;
    }
    return true;
}

void dfs(int now, ll sum) {
    if (now == fn) {
	if (check(sum))
	    ans.insert(sum);
	return;
    }
    ll tmp = 1;
    for (int i = 0; i <= cnt[now]; i++) {
	dfs(now + 1, sum * tmp);
	tmp *= fra[now];
    }
}

void solve(ll n, ll bas) {
    getFra(n);
    dfs(0, 1);
}

bool judge(ll n) {
    if (n == 3 || n == 4 || n == 5|| n == 6)
	return true;
    return false;
}

int main() {
    for (ll i = 2; i < N; i++) {
	if (vis[i]) continue;
	prime[pn++] = i;
	for (ll j = i * i; j < N; j += i)
	    vis[j] = 1;
    }
    int cas = 0;
    scanf("%d", &t);
    while (t--) {
	scanf("%I64d", &n);
	if (judge(n)) {
	    printf("Case #%d: -1\n", ++cas);
	    continue;
	}
	ans.clear();
	for (ll i = 3; i <= 6; i++)
	    solve(n - i, i);
	int out = ans.size();
	printf("Case #%d: %d\n", ++cas, out);
    }
    return 0;
}