正題

---

題目大意

序列$a$有$m$個質數。然后詢問一個數$n$，每次可以使$n=n?n\%a_i$
求最少操作次數。

---

解題思路

首先我們設$f_i$表示由$i$變為0的最少次數，然后有動態轉移$$f_i=min\{f_{i?i\%a_j}\}+1$$
然后我們會發現$f_i$的具有單調性，證明:

$$n?n\%a_i=a_i?\frac{n}{a_i}?$$
假設$f$單調不降，$i=1$時顯然成立
$a_i?\frac{k}{a_i}?$和$a_i?\frac{k+1}{a_i}?$比較
$$\because k+1>k$$
那么就有$$?\frac{k+1}{a_i}?\ge ?\frac{k}{a_i}?$$
因為$f$單調不降
$$f_{?\frac{k+1}{a_i}?}\ge f_{?\frac{k}{a_i}?}$$
即$$f_{k+1}\ge f_k$$

證畢

我們發現每一個$f_i$能更新的序列都是一段連續的序列，且是位置單調不降的。那么我們考慮計算每個$f_i$能更新的區間。

設$f_x$能更新$f_k$，那么有$k\le x+nu{m}_x?1$因為若能更新那么有$k?k\%a_i=i$且對于$k$來說$x$是最大的，那么有$nu{m}_x$就是其中的$a_i$。

但若$k=x+nu{m}_x$那么$x+nu{m}_i?(x+nu{m}_i)\%nu{m}_i=x+nu{m}_i$那么就有更優的方案就不是$x$了。

---

$code$

#pragma GCC optimize(2) %:pragma GCC optimize(3) %:pragma GCC optimize("Ofast") %:pragma GCC optimize("inline") #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> using namespace std; const int M=10000001,N=101000; int m,n,a[N],f[M],Q,num[M],que[N],maxn; queue<int> q; int main() {freopen("data.in","r",stdin);freopen("data.out","w",stdout);scanf("%d%d",&m,&Q);for(int i=0;i<m;i++)scanf("%d",&a[i]);for(int i=1;i<=Q;i++)scanf("%d",&que[i]),maxn=max(maxn,que[i]);memset(f,0x3f,sizeof(f));memset(num,0x3f,sizeof(num));for(int i=0;i<m;i++)for(int j=a[i];j<=maxn;j+=a[i])num[j]=a[i];q.push(0);f[0]=0;num[0]=a[m-1];int now=1;while(!q.empty()&&now<=maxn){int x=q.front();q.pop();if(num[x]>=2147483647/3) continue;int tmp=min(x+num[x]-1,maxn);for(;now<=tmp;now++)f[now]=f[x]+1,q.push(now);}for(int i=1;i<=Q;i++){if(f[que[i]]>=2147483647/3) printf("oo\n");else printf("%d\n",f[que[i]]);} }

總結

以上是生活随笔為你收集整理的jzoj3318-[BOI2013]Brunhilda的生日【数论】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。