$$
\sum_{\varnothing\neq S\subseteq\{1,\dots,n\}}
(-1)^{|S|+1}\left(\prod_{i\in S}p_i\right)\cdot
\frac{\left\lfloor \frac{m}{\prod_{i\in S}p_i}\right\rfloor\left(\left\lfloor \frac{m}{\prod_{i\in S}p_i}\right\rfloor+1\right)}{2}
\pmod{376544743}
$$
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lll = __int128_t;
constexpr int N = 20, P = 376544743;
int p[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> p[i];
}
lll ans = 0;
auto dfs = [&](auto &&self, int dep, int mul, int cnt) {
if (dep == n) {
if (cnt) {
lll res = ((m / mul + 1) * (ll)(m / mul) >> 1) * (lll)mul;
ans += cnt & 1 ? res : -res;
}
return ;
}
self(self, dep + 1, mul, cnt);
if ((ll)mul * p[dep] <= m) {
self(self, dep + 1, mul * p[dep], cnt + 1);
}
};
dfs(dfs, 0, 1, 0);
cout << (int)(ans % P)<< '\n';
return 0;
}
```
实际上，有了剪枝，时间复杂度一个充分紧的上界是 $\Theta(\min(2^n, nm))$，因此不需要对两个数据范围进行分别处理。