TAP2013H

tap2013h.cpp

#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <climits>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <limits>
#include <functional>
#include <map>
#include <queue>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <utility>
#include <set>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define Min(a,b) a < b ? a : b
#define Max(a,b) a > b ? a : b
#define mp make_pair

vector<int> primes;
bool checked[1000010];
int sumPrimes[1000010];
map<int, vector<int> > kays;
int p,  a, b, k, ans;
int level[1000010];


int calc_level(int u) {
	if (level[u] > 0) {
		return level[u];
	}	
	level[u] = calc_level(sumPrimes[u]) + 1;
	kays[level[u]].push_back(u);
	return level[u];

}

void comp_primes() {
	for (int i = 0; i <= 1000002; ++i)
		kays[i] = vector<int>();
	for (int pr = 2; pr <= 1000010; ++pr) {
		if (checked[pr]) continue;
		primes.push_back(pr);
		sumPrimes[pr] = pr;
		level[pr] = 1;
		kays[1].push_back(pr);
		for (int k = 2; pr * k <= 1000000; ++k) {
			checked[k * pr] = true;
			sumPrimes[k * pr] += pr;
		}
	}

	for (int i = 2; i <= 1000002; ++i)
		calc_level(i);

}


int main() {
    ios_base::sync_with_stdio(false);
    comp_primes();
    

    //928604 968019
    cin >> p;
    while (p--) {
    	cin >> a >> b >> k;
    	vector<int>::iterator low = lower_bound(kays[k].begin(), kays[k].end(), a);
    	vector<int>::iterator up = lower_bound(kays[k].begin(), kays[k].end(), b);

    	if (low == kays[k].end()){
    		cout << 0 << '\n';
    	}
    	else if (*low > b){
    		cout << 0 << '\n';
    	}
    	else if (k >= 13)
    		cout << 0 << '\n';
    	else {
    		ans = 0;
    		int mn = low - kays[k].begin();
    		int mx = up - kays[k].begin();
    		if (mx == kays[k].size()) --mx;
    		ans = mx - mn + 1;
    		if (*up >  b) --ans;
    		cout << ans << '\n';
    	}

    }
}