【csust】最小素因子问题（树状数组）

题干：

Description

寒冰射手艾希新学会了一个技能，艾希通过这个技能成为了一名声名远扬的神箭手，从此再也无人敢侵犯弗雷尔卓德！

这个技能的描述如下（假设英雄联盟内的每个人都有一个编号）：

假设艾希有x-1(x>=2)x−1(x>=2)个敌人，每个敌人的编号分别为1\;\;1~\;\;x-1x−1，那么艾希的编号就是xx。艾希每次使用这个技能，那么对于某个敌人，如果这个敌人的编号的最小素因子小于等于艾希的编号的最小素因子，那么艾希能对他造成致命一击。

现在假设已知有tt场战争，每场战争有x-1x−1个敌人，艾希想知道她每场战争使用这个技能能对多少个敌人造成致命一击，由于这个数目太大，她无法计算所以希望你编写一个程序来帮她计算这个结果。

一个数xx的最小素因子：能够整除xx的最小素数。比如2和4的最小素因子是2，3的最小素因子是3。我们知道1不是素数，但是为了题目的完整性，在这里我们定义1的最小素因子为1。

Input

一个正整数t(t<=1000000)t(t<=1000000)，表示有t组数据。

每组数据输入一个整数x(2<=x<=1000000)x(2<=x<=1000000)，表示艾希的编号为xx，且敌人数量为x-1x−1。

Output

对于每组数据输出一个整数ans，表示艾希在这场战争中使用该技能能对ans个敌人造成致命一击。

Sample Input 1

2
2
6

Sample Output 1

1
3

Hint

对于6这个数据，我们知道1~6的每个数的最小素因子依次为1、2、3、2、5、2，因此编号为1、2、4的敌人将会受到致命一击。

解题报告：

注意到需要用到单点更新和区间查询，树状数组离线处理答案就可以了。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 1000000 + 5;
int d[MAX];//处理出每个数字的最小素因子 
int c[MAX];
int ans[MAX];
int lowbit(int x) {return x & -x;}
void update(int x,int val) {
	while(x < MAX) {
		 c[x] += val;
		 x += lowbit(x);
	}
}
int query(int x) {
	int res = 0;
	while(x > 0) {
		res += c[x];
		x -= lowbit(x);
	}
	return res;
}
void db() {
	
	d[1]=1;
	for(int i = 2; i<MAX; i++) {
		if(d[i]) continue; 
		d[i] = i;
		for(int j = i; j<MAX; j+=i) {
			if(!d[j]) d[j] = i;
		}
	}
	
}
int main()
{
	db();
	for(int i = 1; i<MAX; i++) {
		ans[i] = query(d[i]);
		update(d[i],1);
	}
	int t,x;
	cin>>t;
	while(t--) {
		scanf("%d",&x);
		printf("%d\n",ans[x]);
	}
	
	
	return 0 ;
}