codeforces 55D

maksyuki 发表于 oj 分类，标签: DP-数位DP

05 12月 2015

Beautiful numbers

Volodya is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits. We will not argue with this and just count the quantity of beautiful numbers in given ranges.

Input

The first line of the input contains the number of cases t (1 ≤ t ≤ 10). Each of the next t lines contains two natural numbers l_i and r_i (1 ≤ l_i ≤ r_i ≤ 9 ·10¹⁸).

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cin (also you may use %I64d).

Output

Output should contain t numbers — answers to the queries, one number per line — quantities of beautiful numbers in given intervals (from l_i to r_i, inclusively).

Sample test(s)

input

1
1 9

output

input

1
12 15

output

题目类型：数位DP

算法分析：dp[pos][mod][lcm]表示前pos位数除以前pos位数的最小公倍数lcm余数为mod时的个数，由于1~9的最小公倍数为2520，所以mod每次可以直接对2520取模，由于1~2520中满足是最小公倍数的个数才48个，所以可以使用一个映射将最后一维的空间从2520优化到48

/*************************************************
Author        :supermaker
Created Time  :2015/12/5 21:08:41
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

LL dp[22][2666][56], bit[22], cnt[2666];

LL gcd (LL vala, LL valb) {
	if (valb == 0) return vala;
	return gcd (valb, vala % valb);
}

LL SS (int pos, int mod, int lcm, bool flag)
{
	if (pos == 0) return (mod % lcm == 0);
	if (flag && dp[pos][mod][cnt[lcm]] != -1) return dp[pos][mod][cnt[lcm]];
	
	LL res = 0;
	int x = flag ? 9 : bit[pos];
	for (int i = 0; i <= x; i++)
	{
		int ta, tb;
		if (i == 0) ta = lcm;
		else ta = lcm * i / gcd (lcm, i);
		tb = (mod * 10 + i) % 2520;
		res += SS (pos - 1, tb, ta, flag || i < x);
	}
	return flag ? dp[pos][mod][cnt[lcm]] = res : res;
}

LL Calc (LL val)
{
	int len = 0;
	while (val)
	{
		bit[++len] = val % 10;
		val /= 10;
	}
	return SS (len, 0, 1, 0);
}

int main()
{
   //CFF;
	memset (dp, -1, sizeof (dp));
    //CPPFF;
	LL t, id = 0;
	memset (cnt, 0, sizeof (cnt));
	for (int i = 1; i <= 2520; i++) 
		if (2520 % i == 0) 
			cnt[i] = id++;

	scanf ("%I64d", &t);
	while (t--)
	{
		LL vala, valb;
		scanf ("%I64d %I64d", &vala, &valb);
		printf ("%I64d\n", Calc (valb) - Calc (vala - 1));
	}
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

/*************************************************

Author :supermaker

Created Time :2015/12/5 21:08:41

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

LL dp[22][2666][56], bit[22], cnt[2666];

LL gcd (LL vala, LL valb) {

if (valb == 0) return vala;

return gcd (valb, vala % valb);

}

LL SS (int pos, int mod, int lcm, bool flag)

{

if (pos == 0) return (mod % lcm == 0);

if (flag && dp[pos][mod][cnt[lcm]] != -1) return dp[pos][mod][cnt[lcm]];

LL res = 0;

int x = flag ? 9 : bit[pos];

for (int i = 0; i <= x; i++)

{

int ta, tb;

if (i == 0) ta = lcm;

else ta = lcm * i / gcd (lcm, i);

tb = (mod * 10 + i) % 2520;

res += SS (pos - 1, tb, ta, flag || i < x);

}

return flag ? dp[pos][mod][cnt[lcm]] = res : res;

}

LL Calc (LL val)

{

int len = 0;

while (val)

{

bit[++len] = val % 10;

val /= 10;

}

return SS (len, 0, 1, 0);

}

int main()

{

//CFF;

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

//CPPFF;

LL t, id = 0;

memset (cnt, 0, sizeof (cnt));

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

if (2520 % i == 0)

cnt[i] = id++;

scanf ("%I64d", &t);

while (t--)

{

LL vala, valb;

scanf ("%I64d %I64d", &vala, &valb);

printf ("%I64d\n", Calc (valb) - Calc (vala - 1));

}

return 0;

}

hdu4389

Codeforces Round #334(Div.2) (3/5) (Div.1) (1/5)

一	二	三	四	五	六	日
« 6月
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

超客的水墨烟雨

codeforces 55D

分类目录

标签云

书签

近期评论