做旅游攻略去什么网站,南京网站制作学校,住房建设厅官网,网站制作中帐号登录怎么做传送门
题意#xff1a; 思路#xff1a; 一个同于最短路的板子题#xff0c;初始的时候值为0#xff0c;所以设dis[0]0dis[0]0dis[0]0#xff0c;让后选择一个最小的a[i]a[i]a[i]作为basebasebase#xff0c;跑一遍同余最短路就好啦。跑完dis[i]dis[i]dis[i]表示在模b…传送门
题意 思路 一个同于最短路的板子题初始的时候值为0所以设dis[0]0dis[0]0dis[0]0让后选择一个最小的a[i]a[i]a[i]作为basebasebase跑一遍同余最短路就好啦。跑完dis[i]dis[i]dis[i]表示在模basebasebase的意义下能到达iii的最小数。让后问的是区间里的转化为[0,r]−[0,l−1][0,r]-[0,l-1][0,r]−[0,l−1]就好啦。
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n; LL l,r;
int a[N];
LL dis[N];
bool st[N];void dijkstra()
{memset(dis,INF,sizeof(dis));queueintq; q.push(0);dis[0]0;while(q.size()){int uq.front(); q.pop(); st[u]false;for(int i1;in;i){int now(a[i]u)%a[1];if(dis[now]dis[u]a[i]){dis[now]dis[u]a[i];if(!st[now]) q.push(now),st[now]true;}}}
}LL get(LL x)
{LL sum0;for(int i0;ia[1];i) if(dis[i]x) sum(x-dis[i])/a[1]1;return sum;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%lld%lld,n,l,r);for(int i1;in;i) scanf(%d,a[i]);dijkstra();printf(%lld\n,get(r)-get(l-1));return 0;
}
/**/
