【题目链接】 点击打开链接

【题意】

              给你一个数列的第一个数，例如90，那么我每次将这个n分解成素数，90 = 2*3^2*5，那么数列的第二个数是2+3+5 = 10；

              那么数列第三个数有 10 = 2*5 ，2+5 = 7，所以数列的第三个数为7

              第三个数7本身为素数了，那么，定义这个数列的order为3。

              问题，给你a,b,k。求 a<= n <=b 中，多少个以n开头的数列的order为k。

【解题方法】

              我们观察一下数据范围，对应于每一个order的数最多1e6。如果order的取值很小的，那么我们就可以开一个vector直接把每一个order对应的数丢进来，然后找答案的时候二分一下。那么我们如何知道这个结论呢？我们可以验证一下，也可以猜一猜，1个1e6范围之内的素数可以拆成多少个数因子之和？从质因数分解的观点来看，也是logn级别的，所以我们这个开一个大小为20的vector就够了，实际上13就够了，之后的K>=13，答案直接就是0了。


【代码君】


//
//Created by just_sort 2016/12/31
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define MP(x, y) make_pair(x,y)
const int maxn = 1000010;
const int maxm = 2e5;
const int maxs = 10;
const int INF = 1e9;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head
bool vis[maxn] = {0};
int dep[maxn] = {0}, sum[maxn] = {0};
vector <int> v[20];
void init(){
    for(int i = 2; i < maxn; i++){
        if(!vis[i]){
            for(int j = 2 * i; j < maxn; j += i){
                vis[j] = true;
                sum[j] += i;
            }
        }
    }
    for(int i = 2; i < maxn; i++){
        if(!vis[i]){
            dep[i] = 1;
        }
        else{
            dep[i] = dep[sum[i]] + 1;
        }
        v[dep[i]].push_back(i);
    }
}
int main()
{
    init();
//    for(int i  = 0; i < v[10].size(); i++){
//        cout << v[10][i] <<" ";
//    }
    cout<<endl;
    int T, a, b, k;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d%d", &a, &b, &k);
        if(k >= 13){
            printf("0\n");
            continue;
        }
        int l = lower_bound(v[k].begin(), v[k].end(), a) - v[k].begin();
        int r = upper_bound(v[k].begin(), v[k].end(), b) - v[k].begin();
        //cout << l << " " << r << endl;
        cout << r - l << endl;
    }
    return 0;
}