Codeforces55D Beautiful numbers

原题链接

虽然依旧是套模板，但是因为我太弱了，不会建状态，所以去看了题解。。

这里就直接引用我看的题解吧，写的不错的。

题解

//我的代码

#include<cstdio>

#include<cstring>

using namespace std;

const int mod = 2520;

const int N = mod + 10;

typedef long long ll;

int a[20], lc[N], l;

ll f[20][N][50];

inline ll re()

{

	ll x = 0;

	char c = getchar();

	bool p = 0;

	for (; c < '0' || c > '9'; c = getchar())

		p |= c == '-';

	for (; c >= '0' && c <= '9'; c = getchar())

		x = x * 10 + c - '0';

	return p ? -x : x;

}

int gcd(int x, int y)

{

	if (!y)

		return x;

	return gcd(y, x % y);

}

int LCM(int x, int y)

{

	if (!y)

		return x;

	return x / gcd(x, y) * y;

}

ll dfs(int pos, int nw, int lcm, int lm)

{

	if (pos < 0)

		return nw % lcm ? 0 : 1;

	if (!lm && f[pos][nw][lc[lcm]] > -1)

		return f[pos][nw][lc[lcm]];

	int i, k = lm ? a[pos] : 9;

	ll s = 0;

	for (i = 0; i <= k; i++)

		s += dfs(pos - 1, (nw * 10 + i) % mod, LCM(lcm, i), lm && i == a[pos]);

	if (!lm)

		return f[pos][nw][lc[lcm]] = s;

	return s;

}

ll calc(ll x)

{

	int k = 0;

	do

	{

		a[k++] = x % 10;

		x /= 10;

	} while (x > 0);

	return dfs(k - 1, 0, 1, 1);

}

int main()

{

	int i, t;

	ll n, m;

	for (i = 1; i * i <= mod; i++)

		if (!(mod % i))

		{

			lc[mod / i] = ++l;

			lc[i] = ++l;

		}

	memset(f, -1, sizeof(f));

	t = re();

	for (i = 1; i <= t; i++)

	{

		n = re();

		m = re();

		printf("%I64d\n", calc(m) - calc(n - 1));

	}

	return 0;

}

巴特西

Codeforces55D Beautiful numbers

原题链接

最新文章

热门文章