6311. mobitel
给定一个 r 行 s 列的矩阵，每个格子里都有一个正整数。
问如果从左上角走到右下角，且每次只能向右或向下走到相邻格子，那么使得路径上所有数的乘积不小于 n 的路径有多少条？
对于 100% 的数据，1<=r,s<=300,1<=n<=10^6 ，矩阵中的数不超过10^6。
so，一个普通的思想就是设f[i,j,k]表示到(i,j)，乘积为k的总方案
然后发现不仅TLE，还MLE，how to deal with it???
We can find that,there are lots of useless states.So why not cut them down.
我们设f[i,j,k]为当前乘积再乘k就大于n。
然后我们惊讶的发现，k的数量只有\(2\sqrt n\)个，证明可见数论分块
然后简单处理就可以DP了
标签：乘积,格子,分块,数论,路径,DP From： https://www.cnblogs.com/zhy114514/p/18028155