题意

求 n(n\leq 10^{13}) 以内不被 a_1,a_2,\cdots,a_k(k\leq 100,a_i\leq 1000) 中任何数整除的正整数个数。保证 a_i 两两互质。

题解

这个题第一眼看上去像个容斥，于是我整除分块后跑了个 O(k\sqrt n) 的 DP，并把常数卡进了时限。核心代码如下：

for (ll i=1, d; i<=n; i=n/d+1)
    d=n/i, w[++m]=i;
f[0][1]=1;
for (int i=1; i<=k; i++)
{
    if (a[i]==1) { puts("0"); return 0; }
    for (int j=m, p=m; j>=1; j--)
    {
        ll tmp=w[j]*a[i];
        if (tmp>n) continue;
        while (w[p]>tmp) p--;
        // 因为 long long 除法很慢就避免了使用除法
        f[0][p]+=f[1][j];
        f[1][p]+=f[0][j];
    }
}
ll ans=0;
for (int i=1; i<=m; i++)
    ans+=n/w[i]*(f[0][i]-f[1][i]);
printf("%lld\n", ans);

然后交了一发发现 T 了，才看到题目旁边写了时限减半。。只好去看正解。

设 f(n,i) 表示 [1,n] 内不被 a_1,\cdots,a_i 整除的的个数。考虑加入第 a_i，它会筛掉被 a_i 整除但不被 a_1,\cdots,a_{i-1} 整除的数。由于 a_i 两两互质，有 f\left(\left\lfloor\frac{n}{a_i}\right\rfloor,i-1\right) 个这样的数。因此

直接 DP 是 O(nk) 的，然而我们只需要求 f(n,k) 这一个最终状态，所以这里会有很多不需要求的状态。考虑记忆化搜索，只记录 n 较小的状态，其他直接爆搜。这样做并不一定能过，但我们可以让状态尽量集中在 n 小的位置上。考虑将 a_i 排序，搜索到时候从大到小搜，使第一维状态下降得更快一些，就可以过了。

状态数少还有一个原因是，a_i 两两互质时，最坏的情况就是 a_i 从小到大取质数，因此不会有 a_i 都很小的情况。

而我的方法无法被优化是因为所有状态都是最终要用的，记忆化搜索不如递推。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXK=110;
const int MAXM=110000;
const int M=1E5;
int a[MAXK], f[MAXM][MAXK];
ll dp(ll n, int k)
{
    if (k==0) return n;
    if (n<=M&&~f[n][k]) return f[n][k];
    ll ret=dp(n, k-1)-dp(n/a[k], k-1);
    if (n<=M) f[n][k]=ret;
    return ret;
}
int main()
{
//  freopen("CF93E.in", "r", stdin);
//  freopen("CF93E.out", "w", stdout);
    ll n; int k;
    scanf("%lld%d", &n, &k);
    for (int i=1; i<=k; i++) scanf("%d", &a[i]);
    sort(a+1, a+k+1);
    memset(f, -1, sizeof f);
    printf("%lld\n", dp(n, k));
    return 0;
}