problem

给定一个常数k，定义f(x)表示数字x^k的因子的个数。
求f(1)+f(2)+f(3)+…+f(n)的值。
最后结果对1e9+7取模。

Input

输入两个整数n,k(1<=n<=1000000,0<=k<=100)

Output

输出1个整数，表示f(1)+f(2)+…+f(n)的值。
最终结果对1e9+7取模。

Input

3 2

Output

7

Limitation

1s 256MB

Hint

f(1)是数字1^2=1的因子个数，1只有一个因子1，故f(1)=1
f(2)是数字2^2=4的因子个数，4的因子分别是1,2,4，故f(2)=3
f(3)是数字3^2=9的因子个数，9的因子分别是1,3,9，故f(3)=3
f(1)+f(2)+f(3)=7 传送门传送门传送门传送门

思路

首先对于一个数n，进行质因子分解得到：n=p1^a1 * p2^a2 * ….
那么数n的因子个数即为（a1+1）* (a2+1) * ….（每个质因子选几个组合得到）

---

现在要计算的是n^k有多少个因子，由上面性质可知即为
(k * a1+1) * (k * a2+1) * …..

所以只要我们能够在限定时间（1s）内将1~10^6内的数全部都质因数分解就可以了。然后对于每一个询问n和k，i:1~n循环，查询i质因子指数，将它们乘k加1相乘即为i^k的因子个数

代码示例

#include using namespace std; const int maxn=1000005; const int mod=1e9+7; vector<int> prime_factor[maxn]; //先预处理每个数有哪些质因数 void init1()//本机跑了1.303秒 { for(int i=2;iif(prime_factor[i].size()==0){ for(int j=i;jvector<int> factor_zhishu[maxn]; //再预处理每个数的质因子的指数 void init2()//本机跑了1.08s { for(int i=2;iint tp=i; for(int j=0;j0); while(tp%prime_factor[i][j]==0) { factor_zhishu[i][j]++; tp/=prime_factor[i][j]; } } } } int main() { /* clock_t start,finish; double totaltime; start=clock(); //init1(); //init2(); finish=clock(); totaltime=(double)(finish-start)/CLOCKS_PER_SEC; cout<<" 此程序的运行时间为"< init1(); init2(); int n,k; cin>>n>>k; int ans=1; for(int i=2;i<=n;++i){ long long tp=1; for(int j=0;j1))%mod; } ans=(ans+tp)%mod; } cout<return 0; } ///最后在vijos上跑了500ms，评测机单位时间处理量大约是本机的5倍 //本机：intel(R) Core(TM) i5-3470 CPU @3.20GHZ