E/F 题题解

不同与官解的解法，数论分块，时间复杂度 。

大致题意：

给定 ，求 选择 个，使得 不为 的方案数。

解题思路：

一. 初始思想：

已知定值 ，定义 为 选择 个，使得 不为 的方案数。

我们知道每种这样的方案，他们的 是固定的，关于 的计算，考虑枚举所有不为 的 ：

• 若 为 ，那么选择的数必须为 的倍数，这样就有 种选择方案。

• 但是他们的 值需要恰好为 ，也就是说选择的每个数除以 后，他们的 值为 ，这正是总选择方案数 减去 值不为 （除以 后）的方案数 ，即 。

那么我们对其他 也算一遍，能得到下面式子，关于 的计算：

组合数由于选的个数固定，所以可以考虑从 利用比值逐步递推到 ，其中 。由于比值会出现分母，考虑线性求乘法逆元 求出所有逆元，故预处理组合数时间复杂度为 。

时间复杂度 。

发现这东西下标很明显能数论分块，时间复杂度降低到 ，估计可以在 内跑完（

二. 考虑优化：

定义 为 个 需要多少个 ，初始时 其余为 。

从高位往低位推，对于每个 ，，每次将过程中的组合数 的值统计进最终答案 ，用数论分块递推，第一层递推 ，第二层数论分块 ，时间复杂度依旧是 。

但是由于初始只有 有值，所以将 递推后，只有 会有值，接下来推 即可， 的 值均为 。

由性质（OI Wiki上的数论分块引理 ）知，，那么将 递推修改的 ，在第一次推 的时候就已经修改过了，也就是说不会再有新的位置会有值。那么后续的递推只需要推 即可。

递推循环层数降低到 。

总时间复杂度降低为 ，即 。

代码实现：

（去掉了琐碎的开头）

#include<bits/stdc++.h>
#define ll long long
#define MO 1000000007ll
#define MXN 40000002
using namespace std;
ll T=1,n,m,f[MXN],c[MXN],inv[MXN],ans;
void solv(){
    cin>>n>>m;
    inv[1]=1;
    for(ll i=2;i<=n;++i)
        inv[i]=(MO-MO/i)*inv[MO%i]%MO;//求乘法逆元
    c[m]=1;
    for(ll i=m+1;i<=n;++i)
        c[i]=c[i-1]*i%MO*inv[i-m]%MO;//求组合数
    f[n]=1;
    for(ll x=1,y,l;x<=n;x=y+1){//第一层x,y数论分块，l是当前递推下标
        l=n/x,y=n/l;
        for(ll i=2,j,k,num;l/i>=m;i=j+1){//第二层i,j数论分块，k是递推要修改的下标,由于k小于m时组合数为0，所以边界是l/i>=m
            k=l/i,j=l/k;
            num=f[l]*(j-i+1)%MO;//num是f[l]推到f[k]的数量
            ans+=num*c[k]%MO,ans%=MO;
            f[k]-=num,f[k]%=MO;
        }
    }
    cout<<(ans+MO)%MO;
}int main(){while(T--) solv();}