【未完工题解】ABC466_f Many Mod Calculation

1

发现等价于一直拆区间

设有一个区间表示 \([0,d)\)，则用 \(A_i\) 去拆它

则得到了 \(\lfloor \frac{d}{A_i} \rfloor\) 个 \([0,A_i)\) 的区间，和一个 \([0,d \mod A_i]\) 的区间

可以用map来维护

2

全部拆完之后，统计答案即可，注意最后要减去 \(1\) ，因为 \(X+1\) 是取不到的

3：代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
map<int,int,greater<int> > q;
void solve(){int n,x;cin>>n>>x;q.clear();q[x+1]=1;while(n--){int a;cin>>a;for(auto [u,v]:q){if(u<=a) break;q[a]+=u/a*v;if(u%a) q[u%a]+=v;}while(q.begin()->first>a) q.erase(q.begin());}int ans=0;for(auto [u,v]:q) ans+=v;cout<<ans-1<<"\n";
}
signed main(){int t;cin>>t;while(t--) solve();return 0;
}