题解CF93E【Lostborn】

· · 题解

Update

这题显然是个容斥，但是 k \le 100 ，直接容斥会 T 飞。

然后我学校的教练提示我要 DP，我就想了个最初步的：用 dp_{i,j} 表示区间 [1,i] 中被前 j 个数中至少一个数整除的数的个数，答案就是 n-dp_{n,k}。然后转移方程就是

dp_{i,j} = \lfloor \dfrac{i}{a_j} \rfloor + dp_{i,j-1} - dp_{\lfloor {i\over a_j} \rfloor,j-1}

边界就在 j = 0 上。

没什么好解释的，就是最后一项是由于 a 两两互质，所以那 \lfloor \dfrac{i}{a_j} \rfloor 个 a_j 的倍数在后面直接变成 [1,\lfloor \dfrac{i}{a_j} \rfloor] 对整除不影响，也就不影响答案。

但是 O(nk) = 10^{13} \times 100 显然不行。

这时我联想到了数论分块（就那个 O(\sqrt{n}) 计算 \sum\limits_{i=1}^n \lfloor \dfrac{n}{i} \rfloor 的算法），可以发现能影响答案的只有 i \in \{\lfloor \dfrac{n}{i} \rfloor | 1 \le i \le n \} 的部分，而这种 i 只有 O(\sqrt{n}) 个，虽然 O(k \sqrt{n}) 比较极限，但也是可以的。

于是我就用一个 map 来进行记忆化，然后因为多一个 \log 而 TLE 了。

于是我又开了个 O(k \sqrt{n}) 的数组，然后因为开得太大连编译都过不了（都 3 \times 10^8 了，而且还要再乘个 2）

最后教练告诉我可以只把 i 比较小的记忆化并把 a 倒序排序，我算了一下，决定以 2 \times 10^5 为界，因为我用递归实现的记忆化搜索，如果用循环还能大一点，但没必要，然后就 A 了。

之后我试了 n = 10^{13},k = 100 然后 a 为前一百个质数的数据，过了，所以复杂度应该是正确的。

代码（因为倒序排序不方便，所以我是直接排序然后倒着处理的）：

#include<cstdio>
#include<cmath>
#include<algorithm>
#define MAXN 102
#define MAXM 200002
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define fOR(i,a,b) for(int i=a;i<b;i++)
#define rOF(i,a,b) for(int i=a;i>b;i--)
using namespace std;
typedef long long ll;
ll qr(){
    ll x=1,s=0;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')x=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())s=s*10+ch-'0';
    return x*s;
}ll n,k,B,a[MAXN],dp[MAXM][MAXN];
ll dfs(ll n,ll now){
    if(n==0)return 0;if(now==1)return n/a[1];
    if(n<MAXM&&dp[n][now]!=-1)return dp[n][now];
    ll ans=n/a[now]+dfs(n,now-1)-dfs(n/a[now],now-1);
    if(n<MAXM)dp[n][now]=ans;return ans;
}
int main(){
    fOR(i,0,MAXM)fOR(j,0,MAXN)dp[i][j]=-1;
    n=qr();k=qr();
    FOR(i,1,k)a[i]=qr();
    sort(a+1,a+k+1); 
    printf("%I64d",n-dfs(n,k));
    return 0;
}