各种奇怪的韩信问题

发表于 | 分类于

这是两道奇怪的韩信问题

韩信点兵&丧心病狂的韩信大点兵

———————————————

T1

[COGS1786]韩信点兵

题目

韩信是中国军事思想“谋战”派代表人物，被后人奉为“兵仙”、“战神”。“王侯将相”韩信一人全任。“国士无双”、“功高无二，略不世出”是楚汉之时人们对其的评价。作为统帅，他率军出陈仓、定三秦、擒魏、破代、灭赵、降燕、伐齐，直至垓下全歼楚军，无一败绩，天下莫敢与之相争。
相传，韩信带兵打仗时，从不直接清点军队人数。有一次，韩信带1500名兵士打仗，战死四五百人。站3人一排，多出2人；站5人一排，多出4人；站7人一排，多出6人。韩信马上说出人数：1049。
这次，刘邦派韩信带兵N人攻打一座重兵驻扎的城市。城市占领了，可汉军也是伤亡惨重。韩信需要知道汉军至少损失了多少兵力，好向刘邦汇报。
已知韩信发出了M次命令，对于第i次命令，他选择一个素数Pi，要求士兵每Pi人站一排，此时最后一排剩下了ai人。你的任务是帮助韩信求出这种情况下汉军损失兵力的最小值。当然，由于士兵们都很疲惫，他们有可能站错队伍导致韩信得到的数据有误。

INPUT

第一行两个正整数N,M，分别代表最初的军队人数和韩信的询问次数。
接下来有M行，每行两个非负整数Pi，ai，代表韩信选择的素数和此时剩下的人数。
输入保证每个素数各不相同。

OUTPUT

输出一行，一个整数。
若有解，输出最小损失人数。若无解，输出-1.

SAMPLE

INPUT

1500 3
3 2
5 4
7 6

OUTPUT

31

解题报告

CRT裸题
CRT：中国剩余定理
设正整数m1,m2,…,mk两两互素，则同余方程组

x≡a1 (mod m1)

x≡a2 (mod m2)

x≡a3 (mod m3)

. . . . . .

x≡ak (mod mk)

有整数解，并且在模M=m1×m2×…×mk下的解是唯一的，解为

x≡(a1×M1×ny(M1)+…+ak×Mk×ny(Mk))mod M

其中Mi=M/mi，而ny(Mi)为Mi模mi的逆元
代码如下：

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
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long L;
L n;
int m;
L a[11],mod[11];
L M(1),ans(0);
inline void extend_gcd(L a,L b,L &x,L &y){
	if(b==0){
		x=1;
		y=0;
		return;
	}
	extend_gcd(b,a%b,x,y);
	L tmp(x);
	x=y;
	y=tmp-(a/b)*y;
}
inline L CRT(L a[],L m[],int n){
	for(int i=1;i<=n;i++)
		M*=m[i];
	for(int i=1;i<=n;i++){
		L x,y;
		L Mi(M/m[i]);
		extend_gcd(Mi,m[i],x,y);
		ans=(ans+M+Mi*x*a[i])%M;
	}
	//if(ans<0)
	//	ans+=M;
	return ans;
}
inline int gg(){
	freopen("HanXin.in","r",stdin);
	freopen("HanXin.out","w",stdout);
	scanf("%lld%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%lld%lld",&mod[i],&a[i]);
	L ans(CRT(a,mod,m));
	if(ans>n){
		puts("-1");
		return 0;
	}
	while(ans<n)
		ans+=M;
	ans-=M;
	printf("%lld",n-ans);
}
int k(gg());
int main(){;}

需要注意的是，要求的是最小损失人数，稍微处理一下结果即可

———————————————

T2

[COGS2160]丧心病狂的韩信大点兵

题目

懒得粘了，上链接= =
传送门
这道题显然不能用普通的CRT做，因为它们不互质
此时我们就要采用两两合并的思想，假设要合并如下两个方程

x=a1+m1x1

x=a2+m2x2

那么得到

a1+m1x1=a2+m2x2 ☞ m1x1+m2x2=a2-a1

再利用扩展欧几里得解出x1的最小整数解，再代入

x=a1+m1x1

得到x后，合并为一个方程的结果为

y≡x(mod lcm(m1,m2))

这样一直合并下去，最终可以求得解
代码如下：

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
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long L;
int m;
L a[21],mod[21];
inline L gcd(L a,L b){
	return a%b?gcd(b,a%b):b;
}
inline L ext_gcd(L a,L b,L &x,L &y){
	if(b==0){
		x=1;
		y=0;
		return a; 
	}
	L gcd(ext_gcd(b,a%b,x,y));
	L tmp(x);
	x=y;
	y=tmp-(a/b)*y;
	return gcd;
}
inline L ny(L a,L b){
	L x,y;
	L gcd(ext_gcd(a,b,x,y));
	if(gcd!=1)
		return -1;
	return (x%b+b)%b;
}
inline bool merge(L a1,L m1,L a2,L m2,L &a3,L &m3){
	L d(gcd(m1,m2));
	L c=a2-a1;
	if(c%d)
		return false;
	c=(c%m2+m2)%m2;
	m1/=d;
	m2/=d;
	c/=d;
	c*=ny(m1,m2);
	c%=m2;
	c*=m1*d;
	c+=a1;
	m3=m1*m2*d;
	a3=(c%m3+m3)%m3;
	return true;
}
L CRT(L a[],L m[],int n){
	L a1(a[1]),m1(m[1]);
	for(int i=2;i<=n;i++){
		L a2(a[i]),m2(m[i]),a3,m3;
		if(!merge(a1,m1,a2,m2,a3,m3))
			return -1;
		a1=a3;
		m1=m3;
	}
	return (a1%m1+m1)%m1;
}
inline int gg(){
	freopen("weakhanxin.in","r",stdin);
	freopen("weakhanxin.out","w",stdout);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
		scanf("%lld%lld",&mod[i],&a[i]);
	printf("%lld",CRT(a,mod,m));
}
int k(gg());
int main(){;}

ps:这份代码是目前COGS上rk1的代码，在各种0.002s中出现一个0.000s，让我这个鶸鷄感觉有些方= =