数 sqrt 缩小范围
整除分块
1 1 #include <cstdio> 2 2 #include <cstdlib> 3 3 #include <cmath> 4 4 #include <cstring> 5 5 #include <string> 6 6 #include <algorithm> 7 7 #include <iostream> 8 8 using namespace std; 9 9 #define ll long long 10 10 11 11 const int maxn=1e5+10; 12 12 const ll mod=1e9+7; 13 13 const double eps=1e-8; 14 14 15 15 ll f[110][maxn],add[maxn],cnt[maxn]; 16 16 17 17 /** 18 18 大于sqrt(maxvalue)的x， 19 19 肯定是其它数到x，到从x到其它数 20 20 21 21 计数 用 整除分块 22 22 **/ 23 23 24 24 int main() 25 25 { 26 26 ll n,siz,mid,mmid,l,r,i,j,g=0,sum=0; 27 27 scanf("%lld%lld",&siz,&n); 28 28 mmid=sqrt(siz+eps); 29 29 mid=siz/(mmid+1); 30 30 g=0; 31 31 for (l=1;l<=siz;l=r+1) 32 32 { 33 33 ///[l,r] 34 34 r=siz/(siz/l); 35 35 // printf("%lld %lld %lld\n",l,r,siz/l); 36 36 if (siz/l<=mid) 37 37 cnt[siz/l]=r-l+1; 38 38 } 39 39 40 40 for (j=1;j<=mmid;j++) 41 41 f[1][j]=1; 42 42 for (i=2;i<=n;i++) 43 43 { 44 44 g=0; 45 45 for (j=1;j<=mmid;j++) 46 46 (g+=f[i-1][j])%=mod; 47 47 for (j=1;j<=mmid;j++) 48 48 f[i][j]=g; 49 49 50 50 for (l=1;l<=mid;l++) 51 51 add[l]=(add[l-1]+f[i-2][l])%mod; 52 52 53 53 g=0; 54 54 for (l=mid;l>=1;l--) 55 55 { 56 56 (g+=add[l]*cnt[l])%mod; 57 57 (f[i][l]+=g)%=mod; 58 58 } 59 59 } 60 60 61 61 62 62 for (j=1;j<=mmid;j++) 63 63 (sum+=f[n][j])%mod; 64 64 for (l=1;l<=mid;l++) 65 65 { 66 66 add[l]=(add[l-1]+f[n-1][l])%mod; 67 67 (sum+=add[l]*cnt[l])%=mod; 68 68 } 69 69 70 70 /// 71 71 memset(f,0,sizeof(f)); 72 72 g=0; 73 73 for (l=mid;l>=1;l--) 74 74 { 75 75 (g+=cnt[l])%mod; 76 76 f[1][l]=g; 77 77 } 78 78 n--; 79 79 for (i=2;i<=n;i++) 80 80 { 81 81 g=0; 82 82 for (j=1;j<=mmid;j++) 83 83 (g+=f[i-1][j])%=mod; 84 84 for (j=1;j<=mmid;j++) 85 85 f[i][j]=g; 86 86 87 87 for (l=1;l<=mid;l++) 88 88 add[l]=(add[l-1]+f[i-2][l])%mod; 89 89 90 90 g=0; 91 91 for (l=mid;l>=1;l--) 92 92 { 93 93 (g+=add[l]*cnt[l])%mod; 94 94 (f[i][l]+=g)%=mod; 95 95 } 96 96 } 97 97 98 98 for (j=1;j<=mmid;j++) 99 99 (sum+=f[n][j])%mod; 100100 for (l=1;l<=mid;l++) 101101 { 102102 add[l]=(add[l-1]+f[n-1][l])%mod; 103103 (sum+=add[l]*cnt[l])%=mod; 104104 } 105105 106106 107107 printf("%lld",sum); 108108 return 0; 109109 } 110110 /* 111111 special 112112 100=10*10 113113 114114 100 3 115115 1 1 100 116116 2 2 50 117117 3 3 33 118118 4 4 25 119119 5 5 20 120120 6 6 16 121121 7 7 14 122122 8 8 12 123123 9 9 11 124124 10 10 10 125125 /// 126126 11 11 9 127127 12 12 8 128128 13 14 7 129129 15 16 6 130130 17 20 5 131131 21 25 4 132132 26 33 3 133133 34 50 2 134134 51 100 1 135135 136136 137137 23 3 138138 1 1 23 139139 2 2 11 140140 3 3 7 141141 4 4 5 142142 /// 143143 5 5 4 144144 6 7 3 145145 8 11 2 146146 12 23 1 147147 148148 149149 31622*log(n) *100 150150 151151 10 5 152152 1 1 10 153153 2 2 5 154154 3 3 3 155155 156156 4 5 2 157157 6 10 1 158158 159159 */