【2022年11月22日提高A组】数论计算【SPFA】【数学】

思路：

设最小a为min
发现如果$a_1\ast i_1+a_2\ast i_2+\dots \dots +a_n\ast i_n$能达到$k\ast min+t$，那么后面这个加上多少个min，它都是能达到的。
所以spfa出到达t这个余数的最小和是多少，然后直接$(r-dis)/min$得出最多可以加几次

$code$

#include
#include
#include
#include
#define ll long long

using namespace std;

const ll mod = 1e9 + 7;

ll n, l, r, minn = 1e9;
ll a[100], dis[1000010];
bool v[1000010];

void spfa(ll s) {
	queue<ll> q;
	q.push(s);
	memset(dis, 0x7f, sizeof(dis));
	dis[s] = 0;
	v[s] = 1;
	while(!q.empty()) {
		ll x = q.front();
		q.pop();
		for(ll i = 1; i <= n; i ++) {
			ll y = (x + a[i]) % minn;
			if(dis[y] > dis[x] + a[i]) {
				dis[y] = dis[x] + a[i];
				if(!v[y]) {
					q.push(y);
					v[y] = 1;
				}
			}
		}
		v[x] = 0;
	}
}

ll query_(ll x) {
	ll ans = 0;
	for(ll i = 0; i < minn; i ++)
		if(x >= dis[i]) ans = (ans + (x - dis[i]) / minn + 1) % mod;
	return ans;
}

int main() {
	scanf("%lld%lld%lld", &n, &l, &r);
	for(ll i = 1; i <= n; i ++) scanf("%lld", &a[i]), minn = min(a[i], minn);
	spfa(0);
	printf("%lld", (query_(r) - query_(l - 1) + mod) % mod);
	return 0;
}
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