Shen Huang's Blog
0%

Posted on Edited on

其实就是从M算到1.

假如现在算i. 那么找到i ~ M中i的倍数。

看原序列中有多少个是i的倍数，设为cnt.

因为最终假如gcd是i的话，所有数都必须是i的倍数。

那就相当于在cnt个中，要把cnt-(N-K)个变掉，其余的(N-cnt)个要变成i的倍数。

i的倍数为t = M/i 个。

那么符合的数有C[cnt][N-K] (t-1)^(cnt-(N-K)) t^(N-cnt)

这个算出来的是gcd是i的倍数的情况。

减掉gcd是2i,3i….这样的就行了

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/* From: Lich_Amnesia
 * Time: 2013-10-22 10:20:10
 *
 * HDU 4675 2013多校7 J
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl

const int  N = 3e5 + 2;
#define mod 1000000007
typedef long long ll;

ll num[N],d[N],e[N],ans[N];//d表示阶乘
ll power_mod(ll n,ll k){
	ll ret = 1;
	while (k){
		if (k & 1) ret = (ret * n) % mod;
		n = (n*n) % mod;
		k >>= 1;
	}
	return ret;
}
/*求 n个里 选 m 个的方案数*/

ll cal(ll n, ll m){
	return (d[n] * e[m] % mod) * e[n-m] % mod;
}

int main(){
	int n,m,k;
	d[0] = e[0] = 1;
	for (int i = 1; i < N; i++){
		d[i] = d[i-1] * i % mod;
		e[i] = power_mod(d[i],mod-2);
	}
	while (~scanf("%d%d%d",&n,&m,&k)){
		memset(num,0,sizeof(num));
		int cnt;
		for (int i = 0; i < n; i++){
			scanf("%d", &cnt);
			num[cnt]++;
		}
		for (int i = m; i >= 1; i--){
			int sumd = 0;
			for (int j = i; j <= m; j += i){
				sumd += num[j];
			}
			if (sumd < n-k){
				ans[i] = 0;
			}else{
				ans[i] = power_mod(m/i,n-sumd) 
					* power_mod(m/i-1,k-(n-sumd)) % mod;
				ans[i] = ans[i] * cal(sumd,k-(n-sumd)) %mod;
				for (int j = 2 * i; j <= m; j += i){
					ans[i] = (ans[i] - ans[j] + mod) % mod;
				}
			}
		}
		for (int i = 1; i < m; i++)
			cout << ans[i] << &#39; &#39;;
		cout << ans[m] << endl;
	}
	return 0;
}

Posted on Edited on

找一堆Ｋ维点的最长曼哈顿距离，可以用multiset这个STL做。

把绝对值去掉对于每个点来说都有一个$1<<m$的状态0表示+,1表示-，当作2进制来做
然后就是找每个状态下的最大值和最小值减去就行了 </m的状态0表示+,1表示-，当作2进制来做

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/* From: Lich_Amnesia
 * Time: 2013-10-20 08:30:06
 *
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl

multiset<int>mst[(1<<5)+1];
multiset<int>::iterator it1,it2;
int num[60020][10];

int main(){
	int n,m,od;
	while (~scanf("%d%d", &n, &m)){
		for (int i = 0; i < (1<<5); i++)
			mst[i].clear();
		for (int i = 1; i <= n; i++){
			scanf("%d", &od);
			if (od == 0){
				for (int j = 1; j <= m; j++)
					scanf("%d", &num[i][j]);
				for (int j = 0; j < (1 << m); j++){
					int sum = 0;
					for (int k = 1; k <= m; k++){
						if ((1<<(k-1)) & j)
							sum -= num[i][k];
						else sum += num[i][k];
					}
					mst[j].insert(sum);
				}	
			}else {
				int x;
				scanf("%d", &x);
				for (int j = 0; j < (1 << m); j++){
					int sum = 0;
					for (int k = 1; k <= m; k++){
						if ((1<<(k-1)) & j)
							sum -= num[x][k];
						else sum += num[x][k];
					}
					it1 = mst[j].find(sum);
					mst[j].erase(it1);
				}
			}
			int ans = 0;
			for (int j = 0; j < (1 << m); j++){
				it1 = mst[j].end();
				it1--;
				it2 = mst[j].begin();
				ans = max(ans,((*it1) - (*it2)));
			}
			printf("%dn", ans);
		}

	}
	return 0;
}

Posted on Edited on

题意是说求 k % i (i从1到n),直接做肯定是超时的，可以先写一个暴力的程序打表找规律。

1:当n > k 时，n>k的那部分的余数都是 k

2:当n <= k 时，余数呈现等差数列的形式而且等差数列除了最后的那个其他的都是以0结尾，可以枚举k的i分之一正好整除的时候，恰好是等差数列的末项+1和首项，这样就可以做，不过这样还是会超时

还要再加一个优化，比如 12/5 12/6都是2 但是你枚举ndiv时候就多算了，这种多余的可以通过 n == k / (ndiv + 1) 判断进行。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/* From: Lich_Amnesia
 * Time: 2013-10-10 08:37:34
 *
 * POJ 2800 
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
typedef long long ll;

ll solve(ll n,ll k){
	ll sum = 0;
	if (n > k){
		sum += k*(n-k);
		n = k;
	}
	int ndiv = k / n;
	int nnext,low,high;
	while (n > 1){
		nnext = k / (ndiv + 1);
		if (n == nnext){
			sum += k % n;
			n--;
			ndiv = k / n;
			continue;
		}
		low = k % n;
		high = k % (nnext + 1);
		sum += ((low + high) * (n - nnext)) >> 1;
		n = nnext;
		ndiv++;
	}
	return sum;
}

int main(){
	ll n,k;
	while(~scanf("%lld%lld",&n,&k)){
		printf("%lldn",solve(n,k));
	}
	return 0;
}

Posted on Edited on

如果不相交很好求，就是work函数动态规划就行了，可是相交，最多三个交点，也就是在两个人的路中有一个交点，把这种情况给删除掉，就是(1,2)走到了(N,M-1)和(2,1)走到了(N-1,M)的位置

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/* From: Lich_Amnesia
 * Time: 2013-09-29 21:48:22
 *
 * CF 202 Div1 D
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
typedef long long ll;
int N,M;
ll mod = 1000000007;
char s[3100][3100];
ll f[2][3100][3100];
void work(int k,int x,int y){
	if (s[x][y] == '.') f[k][x][y] = 1;
	for (int i = x; i <= N; i++)
		for (int j = y; j <= M; j++)
			if (s[i][j] == &#39;.&#39; && (i!=x || j!=y)){
				f[k][i][j] = (f[k][i-1][j] + f[k][i][j-1]) % mod;
		}
}

int main(){
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; i++)
		scanf("%s", s[i] + 1);
	work(0,1,2);work(1,2,1);
	ll ans = ( f[0][N-1][M]*f[1][N][M-1]%mod - 
		f[0][N][M-1]*f[1][N-1][M]%mod + mod ) % mod;

	//这样能够保证剪掉的都是不相交的
	cout << ans << endl;
	return 0;
}

Posted on Edited on

安排表形成一个矩阵n是已知的求的就是天数x，x*n大约等于sum，记得sum-1因为正好的话会出现问题

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
31
32
33
34
35
36
37
38
39
/* From: Lich_Amnesia
 * Time: 2013-09-29 20:57:37
 * 
 * CF 202div1 A
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
typedef long long ll;
ll s = 0;

int main(){
	int n,x;
	int Max = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		scanf("%d", &x);
		s += x;
		Max = max(x,Max);
	}
	printf("%dn", max(1ll * Max,(s-1)/(n-1) + 1));
	return 0;
}

Posted on Edited on

先找到最长能有多少位，因为最大的数必定是最长的。然后从高位到低位对剩余的进行查找看能不能更大了

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/* CF 202div2 B
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
int main(){
	int v,num[10],min = 1;
	scanf("%d", &v);
	for (int i = 1; i <= 9; i++){
		scanf("%d", &num[i]);
		if (num[min] >= num[i]) min = i;
	}
	int n = v / num[min];
	int remain = v % num[min];
	int j;
	if (n == 0) {
		puts("-1");
		return 0;
	}
	for (int i = 0; i < n; i++){
		for (j = 9; j > min; j--){
			if (remain - num[j] + num[min] >= 0) {
				remain = remain - num[j] + num[min];
				break;
			}
		}
		putchar(&#39;0&#39; + j);
	}
	puts("");
	return 0;
}

Posted on Edited on

简单题

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/* CF 202 div2 A
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
int main(){
	int n,cnt;
	scanf("%d", &n);
	int a = 0, b = 0, c = 0;
	int flag = 1;
	for (int i = 0; i < n; i ++) {
		scanf("%d", &cnt);
		if (cnt == 25 && flag) a ++;
		else if (cnt == 50 && flag) {
			if (a <= 0) flag = 0;
			else {
				a--;b++;
			}
		}else if (cnt == 100 && flag){
			if (b > 0 && a > 0) {b--;a--;}
			else if (b <= 0 && a >= 3){
				a -= 3;
			} else {
				flag = 0;
			}
		}
	}
	if (flag) printf("YESn");
	else printf("NOn");
	return 0;
}

Posted on Edited on

经过别人的诱惑，开始上手Fedora，感觉要比之前自己配置的Ubuntu看起来要好看。于是准备使用，当然装的时候又是各种问题。

在Fedora的官网上下的LiveCD，不知道好不好用，反正我是没装上去。可能得用其他版本啊

一开始就出现硬盘的Grub装不能成功的问题，一种是卡在某个地方，而后换用各种指令，具体可以搜linux硬盘安装的教程，出现了BusyBox的情况，Ubuntu的卸载也这么难弄啊郁闷死

换用第二种方法，用Universal USB Installer弄进U盘里，可是还是不行，根本无法从U盘进入系统，直接是一个小光标一直在闪始终进不去。

然后实在没有办法了。问别人要了一个Fedora 18 的光盘，插入，安装直接就行了。（如果本身就有Linux系统的话，可以直接把/home那个用到Fedora里面不要格式化，把swap和/分区格式化就行了）

这样之后终于把Fedora装上去了，发现Fedora没有中文又没有中文输入法，各种没有YM~

因为出19了，就准备直接升级19，升级的命令如下：

1.首先把系统彻底的更新一遍

1
sudo yum -y upgrade

2.安装fedup

1
sudo yum -y install fedup

3.开始升级，有三个选项可以选，为了方便我选择了网络更新，磁盘有的话不妨试试看光盘或者U盘更新的方法

1
2
sudo fedup --network 19
reboot

4.清理的工作

这里比较恶心的就是fedup可能在更新完后不能正确清理，只能手动来清理了

1
2
sudo fedup  --resetbootloader
sudo fedup --clean

这样grub.cfg和升级后的一些临时文件就能清理掉一些，接着

1
2
sudo yum clean all
sudo yum distro-sync

来把包都更成最新的，然后要清理fedora 18的残留内核，因为是版本升级，所以18的内核就都没用了，都要清掉，命令如下:

1
sudo package-cleanup --oldkernels --count 1

成功后升级你的配置文件，如果不失败，估计是你装得什么东西还对内核有依赖，yum删掉后再清除内核，然后更新grub2配置文件

1
sudo grub2-mkconfig -o /boot/grub2/grub.cfg

更新你的grub2配置文件,重启

1
reboot

如果发现grub2变得很丑的话，进入系统后

1
2
sudo yum -y reinstall gurb2*
sudo grub2-mkconfig -o /boot/grub2/grub/cfg

这样就能解决问题

然后再更新一边你的配置文件

1
sudo grub2-mkconfig -o /boot/grub2/grub/cfg

重启看看，是不是一切都回到原样了

按照这样的方式可以很好地升级到19,不过我的电脑出问题了，没有声音了，然后我就很蛋疼的想是什么问题

后来觉得应该是显卡或者是声卡的问题，于是去网上搜了一个没有声音的教程

改了办法发现没有用，于是只好去网上找显卡驱动，之后找到了Navida的官网

然后就NC了，按照官网的英文提示，一点点地装，一开始装了几个，reboot发现声音好了

继续按照官网往下装，然后就开不了机了。郁闷，如果出现一样的没有声音的问题的话，去官网下，只能下到reboot之前的之后的下了就很危险

然后Fedora就启动不起来了，图形界面字符界面都进不去了，这就郁闷了。

没办法果断重装，具体还是用的光盘。

装完了之后会有好多方面的问题，一个个的解决如下

1.修改软件源为最快的那个并且更新下

1
sudo yum -y install axel yum-plugin-fastestmirror && sudo -y update

2.中文的配置 KDE 的不带中文一开始就是英文看不懂加上各种问题

1
yum list kde*chinese

先找到有哪些可以安装的

然后两个都装是比较好的，不过我装了

1
yum install kde-l10n-Chinese.noarch

这个就行了

然后在system setting的Local然后是Languages里面有Available Languages里面选择就行了
记得注销或者重启

3.配置中文输入法

1
2
yum install ibus
yum install ibus-sunpinyin

先安装Ibus然后在Applications里面的settings里面有一个Input Method然后选择Ibus就行了，当然你的Ibus旁边的那个配置是需要改的，具体的自己看也能看明白，就是添加一个sunpinyin的输入

4.安装chromuim

首先切换到root用户,su - root 您可以可以使用sudu -i

增加Fedora Chromium YUM 源

1
2
cd /etc/yum.repos.d/
wget http://repos.fedorapeople.org/repos/spot/chromium/fedora-chromium-stable.repo

安装Chromium

1
yum install chromium

没有wget的话

1
sudo yum install wget

5.安装g++,c++ gvim

1
2
3
sudo yum install gcc
sudo yum install gcc-c++
sudo yum install gvim

如果出现了如下情况

1
2
3
 // 事务校验出错：  
file /usr/lib64/audit from install of glibc-2.16.31........  
file from package audit-2.2.1-2.fc18.x86_64

再安装一下

1
sudo yum install audit

然后进行安装

  1. 安装flashplayer
1
yum install flash-plugin

具体的指令可能会变，输入flash按Tab来进行补全吧

Posted on Edited on 
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
/* 给出A,B求A^B内的所有约数之和   mod 9901
 *
 * 约数之和，有公式 (p1^0 +  + p1^n1)**(pk^0 +  + pk^nk)
 * 用等比数列求和公式 (p^(n+1)-1)/(p-1)
 * 这里有1/(p-1)，需要求(p-1)关于mod的逆元
 * 但是，
 * 求逆元是有条件的 ax = 1 mod m    存在逆元a^-1 需要 gcd(a,m)  = 1
 *
 * 如果不满足，可用公式 a/b%m = a%(bm)/b
 * 这个公式是没条件的，当然b|a
 * 不过当心bm那里，最大有bm*bm会溢出
 * 不过这题，刚好
 * 对于(p-1)%m==0的那些数据，不会导致溢出
 *
 * 另外一种做法就是二分了
 * 对每个1 +p+..+p^n 
 * n为奇数 : (1++p^n/2) + p^(n/2+1)(1++p^n/2)
 * n为偶数 : (1++p^n/2) + p^n/2(p++p^n/2)
 * 注意维护p
 *
 * */
//#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
typedef long long ll;
ll mod = 9901;
ll pr[100000],pnum[100000];

ll multmod(ll a, ll b){// a* b  % mod
	ll res = 0, base = a;
	while (b){
		if (b & 1) (res += base) %= mod;
		(base <<= 1) %= mod;
		b >>= 1;
	}
	return res;
}

ll powermod(ll prime,ll k){
	ll ret = 1;
	ll a = prime;
	while (k){
		if (k&1) ret = multmod(ret,a);
		a = multmod(a,a);
		k >>= 1;
	}
	return ret;
}

ll solve(ll prime, ll k){//a + a^2 + &hellip;&hellip; + a^k
	if (k == 1) return prime;
	ll halfsum = solve(prime, k >> 1);
	if (k & 1){
		ll half = powermod(prime,(k + 1)>> 1);
		return (halfsum + half + multmod(half,halfsum)) % mod;
	}else {
		ll half = powermod(prime,k >> 1);
		return (halfsum + multmod(half,halfsum)) % mod;
	}
}

int main(){
	ll a,b;
	while (cin >> a >> b){
		if (!b || a <= 1) {
			printf("1n");
			continue;
		}
		int bound = (ceil)(sqrt(a*1.0));
		int cnt = 0; 
		for (int i = 2; i < bound; i++){
			if (a % i == 0){
				pr[cnt] = i;
				pnum[cnt] = 0;
				while (a % i == 0){
					a /= i;
					pnum[cnt] ++;
				}
				pnum[cnt++] *= b;
			}
		}
		if (a > 1) {
			pr[cnt] = a;
			pnum[cnt++] = b;
		}
		ll ans = 1;
		for (int i = 0; i < cnt; i++){
			ll tmp = 1 + solve(pr[i],pnum[i]);
			ans = ans * tmp % mod;

		}
		cout << ans << endl;
	} 
	return 0;	
}

Posted on Edited on

发现用记忆化搜索写数位DP 比较好写

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/* ZOJ 3416 数位DP
 * 一个数是Balanced ，指这个数的力矩为0
 * 如 4139 选支点为3  4*2 + 1*1 = 9*1 
 * 为[x,y]内有多少个Balanced Number   0<=x<=y<=10^18
 *
 * watashi的博客里提到如果 <=10^9 用 sqrt(n)的方法打表，
 * 打印每10w个数之间有多少个Balanced Number
 * 感觉这种方法很好  sqrt(n)
 *
 * 这题数据规模很大10^18，要用数位统计
 *
 * dp的预处理我想的少了一位，最后问别人
 * dp[all,len,total] 表示总长度为all，字符占的长度为len，力矩为total的方案数
 * 如xxx123 即是 dp[6,3,1*3+2*4+3*5]
 *
 * init后，就用数位统计cal(x)统计[0,x]内多少个Balanced Number
 * 枚举位数，枚举该位小于bit[i]的数字j
 * 然后再枚举支点位置，1到len  然后统计
 * （枚举的位置是1到len,第一次遇到枚举的位置可以是pre的东西）
 *
 * 由于一个数的支点只有一个！！！所以不会重复计数
 * "就会发现一个数最多关于一个digit是balanced的
 * （一个严格单调函数最多有一个零点）。
 * 注意到了这一点就会知道，这题是不存在重复计算这种问题的。"
 *
 * 但注意的是0的支点不止一个，所以要减去重复的0
 * 000000  支点任意一个都可以
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
#define ll long long 

int dig[20];
ll dp[20][20][10000]; 

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

ll dfs(int pos,int bal,int prenum,bool islim){
	if (prenum < 0) return 0;//从后向前枚举的所以不能小于0
	if (pos == -1) return prenum == 0;
	if (!islim && dp[pos][bal][prenum] != -1){
		return dp[pos][bal][prenum];
	}
	int end = islim ? dig[pos] : 9;
	ll ans = 0; 
	for (int i = 0; i <= end; i++){
		ans += dfs(pos-1,bal,prenum+(pos-bal)*i,islim && i == end);
	}
	if (!islim)
		dp[pos][bal][prenum] = ans;
	return ans;

}

ll cal(ll n){
	int num = 0;
	while (n){
		dig[num++] = n % 10;
		n /= 10;
	}
	ll ret = 0;
	for (int i = 0; i < num; i++)
		ret += dfs(num-1,i,0,1);
	return ret-num+1;//因为0的支点可以整个数的数位减去重复的
	//比如00000支点任意一个都可以
}

int main(){
	int t;
	init();	
	ll l,r;

	for (scanf("%d", &t); t--;){
		cin >> l >> r;
		cout << cal(r) - cal(l-1) << endl;
	}
	return 0;
}