「CF55D」Beautiful numbers

传送门

Luogu

解题思路

毒瘤数位DP，发现一个前缀我们只需要记录它对 \(\operatorname{lcm}(1,2,3,\cdots,9)=2520\) 取模的值即可，所以我们在 DP 时记录一下当前的前缀模2520的值，以及前缀每一位数字的 \(\operatorname{lcm}\) 即可，至于空间的问题，只需要对2520的所有约数离散一下就好了。

细节注意事项

咕咕咕

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#define rg register

using namespace std;

typedef long long LL;

int a[20], xxx, mp[2520]; LL dp[20][2520][50];

inline LL dfs(int now, int las, int mod, int lim) {

	if (!now) return las % mod == 0;

	if (!lim && dp[now][las][mp[mod]] != -1) return dp[now][las][mp[mod]];

	LL res = 0; int tp = lim ? a[now] : 9;

	for (rg int j = 0; j <= tp; ++j)

		res += dfs(now - 1, (las * 10 + j) % 2520, j == 0 ? mod : j * mod / __gcd(j, mod), lim && j == tp);

	if (!lim) dp[now][las][mp[mod]] = res;

	return res;

}

inline LL solve(LL x) {

	int n = 0;

	for (rg LL i = x; i; i /= 10) a[++n] = i % 10;

	return dfs(n, 0, 1, 1);

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("in.in", "r", stdin);

#endif

	memset(dp, -1, sizeof dp);

	for (rg int i = 1; i <= 2520; ++i)

		if (2520 % i == 0) mp[i] = ++xxx;

	int T; cin >> T;

	for (LL l, r; T--; )

		cin >> l >> r, cout << solve(r) - solve(l - 1) << endl;

	return 0;

}

完结撒花 \(qwq\)

巴特西

「CF55D」Beautiful numbers

解题思路

细节注意事项

参考代码

最新文章

热门文章