51Nod-1232-完美数

ACM模版

描述

题解

这里要求数的值整除以所有位的值,除 0 以外,所以也就很容易想到,这个数一定是要整除这些位数的最小公倍数,而这些数范围是 1∼9 ,所以最小公倍数最大也就是 2520,记录数对 2520 的余数即可,并且这里由于公倍数的数量很少,不超过五十个,所以先离散化一下优化优化,剩下的就是典型的数位 dp了。

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

const ll MOD = 2520;
const int MAXN = 22;
const int MAXM = 55;

ll x, y;
int dig[MAXN];
int _hash[MOD + 10];

ll dp[MAXN][MAXM][MOD + 10];

ll gcd(ll x, ll y)
{
    if (y == 0)
    {
        return x;
    }
    else
    {
        return gcd(y, x % y);
    }
}

void init()
{
    memset(dp, -1, sizeof(dp));

    int cnt = 0;
    for (int i = 1; i <= MOD; i++)
    {
        if (MOD % i == 0)
        {
            cnt++;
            _hash[i] = cnt;
        }
    }
}

ll dfs(ll n, ll tag = 1, ll lcm = 1, ll num = 0)
{
    if (n <= 0)
    {
        return num % lcm == 0;
    }

    if (!tag && dp[n][_hash[lcm]][num] != -1)
    {
        return dp[n][_hash[lcm]][num];
    }

    ll ans = 0;
    int end = (tag == 1) ? dig[n] : 9;
    for (int i = 0; i <= end; i++)
    {
        ll lcm_tmp;
        int m = (num * 10 + i) % MOD;
        if (i != 0)
        {
            lcm_tmp = lcm / gcd(lcm, i) * i;
        }
        else
        {
            lcm_tmp = lcm;
        }

        ans += dfs(n - 1, tag & (i == end), lcm_tmp, m);
    }

    if (!tag)
    {
        dp[n][_hash[lcm]][num] = ans;
    }

    return ans;
}

ll solve(ll x)
{
    int cnt = 0;
    memset(dig, 0, sizeof(dig));

    while (x)
    {
        cnt++;
        dig[cnt] = x % 10;
        x /= 10;
    }

    ll r = dfs(cnt);

    return r;
}

int main()
{
    init();

    int T;
    scanf("%d", &T);

    while (T--)
    {
        scanf("%lld%lld", &x, &y);
        printf("%lld\n", solve(y) - solve(x - 1));
    }

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • cpu分析利器 — async-profiler

    async-profiler是一款采集分析java性能的工具,翻译一下github上的项目介绍:

    龟仙老人
  • AkShare-股票数据-美港目标价

    目标地址: https://www.ushknews.com/report.html

    数据科学实战
  • 51Nod 1182 完美字符串(字符串处理 贪心 Facebook Hacker Cup选拔)

    1182 完美字符串 ?             题目来源:                         Facebook Hacker Cup选拔    ...

    Angel_Kitty
  • LeetCode 507. 完美数

    对于一个 正整数,如果它和除了它自身以外的所有正因子之和相等,我们称它为“完美数”。

    Michael阿明
  • Python识别完美数

    完美数(perfect number,又称完全数)指,它所有的真因子(即除了自身以外的因子)和,恰好等于它自身。

    double
  • 1030. 完美数列(25)

    给定一个正整数数列,和正整数p,设这个数列中的最大值是M,最小值是m,如果M <= m * p,则称这个数列是完美数列。

    AI那点小事
  • 数制转换itoa atoi int转字符串 字符串转int string转int int转string

    C语言提供了几个标准库函数,可以将任意类型(整型、长整型、浮点型等)的数字转换为字符串,下面列举了各函数的方法及其说明。 1.itoa():将整型值转换为字符...

    风骨散人Chiam
  • 【leetcode刷题】T203-完美数

    https://leetcode-cn.com/problems/perfect-number/

    木又AI帮
  • 1030 完美数列 (25 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051

扫码关注云+社区

领取腾讯云代金券