源代码:
// clang-format off
// /*[*/#include<stdio.h>//
// #include<stdlib.h>//]++++[->++[->+>++++<<]<][(c)2023]
// #ifndef e//[o
// #include<string.h>//]![misaka.c,size=3808,crc=d0ec3b36][
// #define e 0x1//
// typedef struct{int d,b,o,P;char*q,*p;}f;int p,q,d,b,_=0//|
// #include __FILE__//]>>>[->+>++<<]<[-<<+>>>++<]>>+MISAKA*IMOUTO
// #undef e//[->[-<<+<+<+>>>>]<<<<<++[->>+>>>+<<<<<]>+>+++>+++[>]]b
// #define e(c)/**/if((_!=__LINE__?(_=__LINE__):0)){c;}//[20002,+[-.+]
// ,O,i=0,Q=sizeof(f);static f*P;static FILE*t;static const char*o[]={//
// "\n\40\"8oCan\40not\40open %s\n\0aaFbfeccdeaEbgecbbcda6bcedd#e(bbed$bbd",
// "a6bgcdbbccd#ead$c%bcdea7bccde*b$eebbdda9bsdbeccdbbecdcbbcceed#eaa&bae$cbe",
// "e&cbdd$eldbdeedbbdede)bdcdea&bbde1bedbbcc&b#ccdee&bdcdea'bbcd)e'bad(bae&bccd",
// "e&bbda1bdcdee$bbce#b$c&bdedcd%ecdca4bhcdeebbcd#e$b#ecdcc$bccda7bbcc#e#d%c*bbda",
// ">bad/bbda"};static int S(){return(o[p][q]);}static/**/int/**/Z=0 ;void/**/z(int//
// l){if(/**/Z-l){Z=l;q++;if(p<b*5&&!S()){p+=b;q=0;}}}int main(int I, /**/char**l){//
// d=sizeof(f*);if(1<(O=_)){b=((sizeof(o)/sizeof(char*))-1)/4;q=22; p= 0;while(p<b*5){
// /*<*/if(Z-1){d=S()>96;i=S()-(d?96:32) ;q++;if(p<b*5&&!S()){p+=b; q= 0;}Z=1;}/*[[*/
// while(i){_=o[0][S()-97];I=_-10?b:1; for( ;I--;)putchar(_ );if (! --i||d)z(~i );}
// if(p==b*5&&O){p-=b;O--;}}return 0U; }if(! (P=( f*)calloc /*]*/ (Q ,I)))return 1;
// {;}for(_=p=1;p<I;p++){e(q=1);while (q< p&& strcmp( l[p ] ,l[(q)]))++ q;
// t=stdin;if(q<p){(void)memcpy/* " */ (&P [p],&P [q ] ,Q);continue ;}
//if(strcmp(l[p],"-")){t=fopen(l [ p] ,"rb" ) ;if(!t ){{;} ;
//printf(05+*o,l[p ]);return+1; {;} }}_=b= 1<<16 ;
//*&O=5;do{if(!(P[p].q=realloc (P[p].q,(P[p].P += b)+1))){return 01;}O &=72 /
//6/*][*/;P[p].o+=d=fread(P[p] .q +P[ p ]. o, 1,b,t) ;}//
// while(d==b) ;P [p].q[ P[ p] .o ]= 012;d =0;
// e(fclose(t ) );P [p] .p =P[ p] .q;if (O)
// {for(;d<P[ p] .o ;d= q+ 1) {q= d;
// while(q<P[ p].o&&P[ p].q[q]- 10 ){
// q++;}b=q-d; _=P [p]. d ;
// if(b>_){/*]b */
// P[p].d=b;}{; }
// #undef/*pqdz'.*/ e// ;
// #define/*s8qdb]*/e/**/0 //
// //<<.<<.----.>.<<.>++.++< .[>]
// /*P[*/P[p].b++;continue;}}}t= stdout;
// for (p=1;p<I;p++){/**/if(P[p].b>i ){i=P[p].b;}}
// if (O){for(p=0;p<i;p++){q=0;/*[*/while(I >++q){_=P[q].p-P[q ].q;
//b= 0;if(_<P[q ].o){while(012-*P[q].p) {putchar(*(P[q].p++));b++;}P[q]. p++;
//} ;while (P[ q].d>b++)putchar(040);} putchar(10);}return 0;}p =1;
// for(; p<I ;p++)fwrite(P[p] .q,P[ p].o,1,t);return 0 ;}//
// #/*] ]<. [-]<[-]<[- ]<[ -]< [- ]<;*/elif e //b
// |(1 << ( __LINE__ /* >> `*//45)) | 01U
// # /* */ endif //
// clang-format on
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << ' ' << x << endl;
#define int long long
typedef pair<int, int> pii;
namespace Larry76 {
const int MAX_SIZE = 6e6;
const int INF = 0x7f7f7f7f7f7f7f7fll;
const double eps = 1e-9;
const int MOD = 1e9 + 7;
#define mul(a, b) (((a) % MOD * ((b) % MOD)) % MOD)
#define minus(a, b) \
((((a) - (b)) < 0) \
? ((a) - (b) + MOD) \
: ((((a) - (b)) >= MOD) ? ((a) - (b)-MOD) : ((a) - (b))))
#define add(a, b) (((a) + (b) >= MOD) ? ((a) + (b)-MOD) : ((a) + (b)))
#define inv(x) (fastpow(x, MOD - 2))
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
int fastpow(int base, int index) {
int ans = 1;
while (index) {
if (index & 1) ans = mul(ans, base);
base = mul(base, base);
index >>= 1;
}
return ans;
}
inline int gcd(int A, int B) {
int C;
while (B) C = B, B = A % B, A = C;
return A;
}
int exgcd(int A, int B, int &X, int &Y) {
if (B == 0) {
X = 1, Y = 0;
return A;
}
int res = exgcd(B, A % B, X, Y);
int temp = Y;
Y = X - A / B * Y;
X = temp;
return res;
}
///////////// Start Coding //////////////
#undef add
int head[MAX_SIZE];
int Next[MAX_SIZE];
int ver[MAX_SIZE];
int edge[MAX_SIZE];
int tot = 1;
void add(int u, int v, int c = 0) {
ver[++tot] = v;
edge[tot] = c;
Next[tot] = head[u];
head[u] = tot;
}
const int MAX_VERTEX = 6e5;
int d[MAX_VERTEX];
bitset<MAX_VERTEX> vis;
bool SPFA(int s) {
memset(d, 0x7f, sizeof(d));
queue<int> q;
q.push(s);
d[s] = 0;
vis[s] = 1;
while (q.size()) {
int u = q.front();
q.pop();
for (int i = head[u]; i; i = Next[i]) {
int v = ver[i];
if (d[v] > d[u] + edge[i]) {
d[v] = d[u] + edge[i];
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
vis[u] = 0;
}
return true;
}
int n, l, r;
int a[20];
void main() {
n = read();
l = read();
r = read();
int x = INF;
for (int i = 1; i <= n; i++) {
a[i] = read();
x = min(x, a[i]);
}
for (int i = 0; i < x; ++i) {
for (int j = 1; j <= n; j++) {
add(i, (i + a[j]) % x, (i + a[j]) / x);
}
}
SPFA(0);
int ans = 0;
for (int i = 0; i < x; i++) {
if (d[i] * x + i <= r) {
int L = max(d[i] * x + i, l);
int R = r;
if (L / x < R / x) {
ans += R / x - L / x - 1;
if (L <= L / x * x + i && L / x * x + i <= R) ++ans;
if (L <= R / x * x + i && R / x * x + i <= R) ++ans;
} else if (L <= L / x * x + i && L / x * x + i <= R) {
++ans;
}
}
}
printf("%lld\n", ans);
return void();
}
} // namespace Larry76
signed main() {
Larry76::main();
return (0 ^ 0);
}
提前感谢各位大佬了/bx