直接推公式没有推出来
看了题解才会做。。
首先能够确定前面几个数的gcd一定是2^j * 3^k, 其中k<=1
那么可以用dp[i][j][k]来表示到第i位的gcd是2^j*3^k
f(j,k) 为 n / 2^j / 3^k
那么状态转移有
dp[i+1][j][k]=dp[i][j][k]*( f(j,k)-i ); //继承前一状态
dp[i+1][j-1][k]=dp[i][j][k]*( f(j-1,k)-f(j,k) );
dp[i+1][j][k-1]=dp[i][j][k]*( f(j,k-1)-f(j,k) );
#include <iostream> using namespace std; #define mod 1000000007 int n,dp[1000005][21][2]; int f(int x,int y) { int tmp=(1<<x); if (y) tmp*=3; return n/tmp; } int main() { scanf("%d",&n); int p=0; while ((1<<p)<=n) p++; p--; dp[1][p][0]=1; if ((1<<(p-1))*3<=n) dp[1][p-1][1]=1; for (int i=1;i<n;i++) { for (int x=0;x<=p;x++) { for (int y=0;y<=1;y++) { dp[i+1][x][y]=(dp[i+1][x][y]+1LL*dp[i][x][y]*(f(x,y)-i))%mod; if (x) dp[i+1][x-1][y]=(dp[i+1][x-1][y]+1LL*dp[i][x][y]*(f(x-1,y)-f(x,y)))%mod; if (y) dp[i+1][x][y-1]=(dp[i+1][x][y-1]+1LL*dp[i][x][y]*(f(x,y-1)-f(x,y)))%mod; } } } printf("%d",dp[n][0][0]); }
转载于:https://www.cnblogs.com/zsben991126/p/10987339.html
相关资源：ACM数论——ppt（天津大学）