前言:

这题难点在于复杂度分析.

实现:

首先很容易想到k假如不是质数答案为0.因为假如k不是质数,那么它一定可以写成比它小的数相乘.
其次假如答案可行,必定是大于等于k的质数的乘积的形式.因为假设不是比k的质数乘积,就是利用了到的质数.这是不行的.
有了这两点,暴力的代码应该是都会写的..区间的就等于.然后令是以内能被整除,不能被到整除的答案即可.至于cal怎么算,是利用容斥算的,是区间的总答案,同时也是乘的那个系数.前面讲到了,这个系数不能是到的数.然后递归下就好了.

#include <iostream>
using namespace std;
bool _prime(int x)
 {
     for(int i=2;i<=x/i;i++)
     {
         if(x%i==0)    return false;
    }return true;
 }//O(sqrt(x))

int cal(int n,int k)//计算n以内,能被k整除但不能被2~k-1整除的数量. 
{
    if(!_prime(k))    return 0;
    if(k>=n)        return (k==n);
    int res=n/k;
    for(int i=2;i<k&&i<=n/k;i++)
    {
        res-=cal(n/k,i);
    }return res;
}

int main()
{
    int a,b,k;
    scanf("%d%d%d",&a,&b,&k);
    printf("%d\n",cal(b,k)-cal(a-1,k));
    return 0;
}

复杂度分析:

当k和n都很接近时,复杂度很低.(n/k)
当k很大时,复杂度也很低.(k>=n)
当k很小n很大时,复杂度也不高.(i<=k)
那么复杂度最高的时是:当k取sqrt(n)时,而n取1e9.
此时我们第一个for循环会运行sqrt(1e9)次,然后它的子程序的n就成了sqrt(1e9)了,而它子程序的k的复杂度最高的还是sqrt(n)时.如此分析时间复杂度应是接近根号的.