數論只會 for 回圈 （數學+分塊+記憶化）

題目鏈接：點擊這里

題目大意：
給定 n , k n,k n,k 計算函式：
f ( n , k ) = { 1 i f k = 0 ∑ i = 1 n ? l o g 2 i ? f ( ? n i ? , k ? 1 ) i f k ≥ 1 f(n,k)= \begin{cases} 1 &if\ k=0\\ \sum_{i=1}^n\lceil log_2i \rceil f(\lfloor \frac ni \rfloor,k-1) &ifk \ge 1 \end{cases} f(n,k)={1∑i=1n??log2?i?f(?in??,k?1)?if k=0ifk≥1?
答案對 1 e 9 + 7 1e9+7 1e9+7 取模

題目分析：
分析這個式子顯然有 f ( 1 , k ) = 0 ( k ≥ 1 ) f(1,k)=0(k \ge 1) f(1,k)=0(k≥1)
發現 f ( ? n i ? , k ? 1 ) f(\lfloor \frac ni \rfloor,k-1) f(?in??,k?1) 中的 ? n i ? \lfloor \frac ni \rfloor ?in?? 是一個典型的分塊式，可以分塊處理，而且 ? n i ? = 1 \lfloor \frac ni \rfloor=1 ?in??=1 這個塊大小為 n 2 \frac n2 2n? ，利用這個性質我們可以得到 f ( n , k ) f(n,k) f(n,k) 中 f ( 1 , x ) f(1,x) f(1,x) 的數目近似為 l o g 2 n log_2n log2?n (調和級數)
因此對于 n ≥ l o g 2 ( 1 e 8 ) ≥ 27 n \ge log_2(1e8) \ge 27 n≥log2?(1e8)≥27 的資料答案就是 0 0 0
對于 n ≤ l o g 2 ( 1 e 8 ) n \le log_2(1e8) n≤log2?(1e8) 的情況我們可以列舉 ? l o g 2 i ? \lceil log_2i \rceil ?log2?i? 然后利用分塊處理 f ( ? n i ? , k ? 1 ) f(\lfloor \frac ni \rfloor,k-1) f(?in??,k?1) ，記憶化+遞回求解即可

具體細節見代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<unordered_map>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
int read()
{
	int res = 0,flag = 1;
	char ch = getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch == '-') flag = -1;
		ch = getchar();
	}
	while(ch>='0' && ch<='9')
	{
		res = (res<<3)+(res<<1)+(ch^48);//res*10+ch-'0';
		ch = getchar();
	}
	return res*flag;
}
const int maxn = 5e3+5;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-8;
unordered_map<int,int>mp[27];
int f(int n,int k)
{
	if(k >= 27) return 0;
	if(mp[k].find(n) != mp[k].end())
		return mp[k][n];
	if(k == 0) return mp[k][n] = 1;
	else {
		int& tmp = mp[k][n];
		for(int i = 1;(1<<i) <= 2*n;i++)
		{
			int l = (1<<(i-1))+1,r = min(1<<i,n),rr;
			for(int j = l;j <= r;j = rr+1)
			{
				int pos = n/j;
				rr = min(r,n/pos);
				tmp = (tmp+1ll*i*(rr-j+1)%mod*f(pos,k-1))%mod;
			}
		}
		return tmp;
	}
}
int main()
{
	int n = read(),k = read();
	printf("%d\n",f(n,k));
	return 0;
}