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 条评论
登录 后参与评论

相关文章

来自专栏Android小菜鸡

Android语音录制,语音发送

这是一个录音的例子,可用于IM的语音发送,OA的语音留言等。 首先我们需要引入权限:

52920
来自专栏zaking's

RFC2616-HTTP1.1-Methods(方法规定部分—单词注释版)

12650
来自专栏debugeeker的专栏

sedna进行xquery查询

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

8910
来自专栏.net core新时代

Spire.Doc组件读取与写入Word

  之前写了一篇开源组件DocX读写word的文章,当时时间比较匆忙选了这个组件,使用过程中还是有些不便,不能提前定义好模版,插入Form表单域进行替换。最近无...

297100
来自专栏zaking's

RFC2616-HTTP1.1-Header Field Definitions(头字段规定部分—单词注释版)

16120
来自专栏菩提树下的杨过

ExtJs学习笔记(3)_GridPanel[XML做数据源]

这一节,将学习到除了用JSON做GridPanel的数据源外,还可以使用XML 一。静态示例 1.xml文件内容: <?xml version="1.0...

23880
来自专栏杂烩

分布式服务框架之Dubbo整合Spring项目(二)

11420
来自专栏黑白安全

ctf工具包 ctf Toolkit 渗透测试工具包 隐秘数据破解

│ ├── caidao-20160620-www.maicaidao.com.7z

1.1K20
来自专栏游戏杂谈

基于SOUI开发一个简单的小工具

Duilib 很久不维护了,而很多不同的分支,似乎都不太维护。微信 Windows 的版本是基于 Duilib 进行开发的,说明应该还是很广泛的。

46330
来自专栏华仔的技术笔记

Spectrum光谱链共识算法的分析

Spectrum(光谱链)是SmartMesh生态下的公链,承载去中心化Mesh网络实现万物互联dapp的底层公链。由Payment Channel的建构的Sm...

10530

扫码关注云+社区

领取腾讯云代金券