Codeforces

Luogu

分析

根据一些小学奥数知识可以知道第一个数应该是 $2^x3^y$ 的形式，而且 $y\in\{0,1\}$ ，因为 $>3$ 的质因子我们换成 $2^k$ 更优，$3^2$ 换成 $2^3$ 更优。为了方便设 $m=\lfloor\log_2 n\rfloor$。

考虑 DP。设 $dp_{i,x,y}$ 表示前 $i$ 个数，当前的 $\gcd$ 是 $2^x3^y$ 的方案数，转移有三种

• $\gcd$ 不变，则我们需要选一个 $2^x3^y$ 的倍数，因为之前已经选去了 $i-1$ 个，所以有 $dp_{i,x,y}\leftarrow dp_{i-1,x,y}\times\left(\left\lfloor\frac{n}{2^x3^y}\right\rfloor-(i-1)\right)$。
• $\gcd$ 除以 $2$，则我们需要选一个是 $2^x3^y$ 的倍数、不是 $2^{x+1}3^y$ 的倍数的数，所以有 $dp_{i,x,y}\leftarrow dp_{i,x+1,y}\times\left(\big\lfloor\frac{n}{2^x3^y}\big\rfloor-\big\lfloor\frac{n}{2^{x+1}3^y}\big\rfloor\right)$。这里并不需要减去 $i-1$，因为前 $i-1$ 个数一定是 $2^{x+1}3^y$ 的倍数。
• $\gcd$ 除以 $3$，和上面一种类似。

边界是 $dp_{1,m,0}=1$ 和 $dp_{1,m-1,1}=1$（如果 $2^{m-1}\times 3\leq n$ 的话）。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;
const int mod=1e9+7;

int n,m,dp[N][20][2];

int f(int x,int y) { return y?(1<<x)*3:(1<<x); }

int main() {
    n=read(),m=log2(n);
    dp[1][m][0]=1;
    if (f(m-1,1)<=n) dp[1][m-1][1]=1;
    for (int i=2;i<=n;++i)
        for (int x=0;x<=m;++x)
            for (int y=0;y<=1;++y) {
                dp[i][x][y]=(dp[i][x][y]+1ll*dp[i-1][x][y]*(n/f(x,y)-(i-1)))%mod;
                if (x<m) dp[i][x][y]=(dp[i][x][y]+1ll*dp[i-1][x+1][y]*(n/f(x,y)-n/f(x+1,y)))%mod;
                if (y<1) dp[i][x][y]=(dp[i][x][y]+1ll*dp[i-1][x][y+1]*(n/f(x,y)-n/f(x,y+1)))%mod;
            }
    printf("%d\n",dp[n][0][0]);
    return 0;
}