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; }