首页 > 代码库 > Lucky Number

Lucky Number

2024-07-17 05:12:40   222人阅读

题目链接

  • 题意：
    输入一个n，求在多少个x进制下只含有3、4、5、6
    (1<=n<=1e12)
  • 分析：
    用的是比较常规的方式。对于n，最后一位必然是这四个数中的一个，可以枚举末位i，那么n-i，一定能被x进制整除，也就是说，可以找到n-i的所有因子，在这之中找到可能是答案的因子即可。
const int MAXN = 1100000;

int prime[MAXN], tot;
bool check[MAXN];

void init()
{
    FE(i, 2, MAXN)
    {
        if (!check[i])
            prime[tot++] = i;
        for (int j = 0; j < tot && i <= MAXN / prime[j]; j++)
        {
            check[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
}

struct Fac
{
    LL val, num;
} fac[200];
int cnt;
vector<LL> vt;
int ok(LL t, LL i)
{
    t /= i;
    while (t)
    {
        if (t % i != 3 && t % i != 4 && t % i != 5 && t % i != 6)
            break;
        t /= i;
    }
    if (!t)
        return 1;
    return 0;
}
int used;
void dfs(int pos, LL val, LL n)
{
    if (pos == cnt)
    {
        if (val > used && ok(n, val))
            vt.push_back(val);
        return;
    }
    LL t = 1;
    FE(i, 0, fac[pos].num)
    {
        dfs(pos + 1, val * t, n);
        t *= fac[pos].val;
    }
}
int fun(LL n)
{
    vt.clear();
    cnt = 0;
    LL nn = n;
    for (int i = 0; i < tot && prime[i] <= n / prime[i]; i++)
        if (n % prime[i] == 0)
        {
            fac[cnt].val = prime[i];
            fac[cnt].num = 0;
            while (n % prime[i] == 0)
            {
                n /= prime[i];
                fac[cnt].num++;
            }
            cnt++;
        }
    if (n > 1)
    {
        fac[cnt].val = n;
        fac[cnt].num = 1;
        cnt++;
    }
    dfs(0, 1, nn);
    vt.erase(unique(all(vt)), vt.end());
    REP(i, vt.size())
    {
        debugI(vt[i]);
    }
    return vt.size();
}
int solve(LL n)
{
    int ret = 0;
    for (used = 3; used <= 6; used++)
        ret += fun(n - used);
    return ret;
}

int main()
{
    init();
    int T;
    RI(T);
    FE(kase, 1, T)
    {
        LL n;
        cin >> n;
        if (n < 3)
            printf("Case #%d: 0\n", kase);
        else if (n <= 6)
            printf("Case #%d: -1\n", kase);
        else
            printf("Case #%d: %d\n", kase, solve(n));
    }
    return 0;
}



联系
我们