老规矩，先放原题
这题问小于n的数中有几个数的最大因数是d。有T \le 10^6组数据，并且2 \le d。
首先，枚举所有小于n的整数明显是不可取的，不说判断因数的复杂度是\sqrt n，单是n \le 10^9就够我喝一壶了。
想一想，d是因数，这样的数x一定能表示成x=k \cdot d的形式，那么，我们可以枚举所有k，需要枚举的数大大减少了。进一步的，k不能喧宾夺主，所以必有k,这下，即使在最坏的情况下，也有k<\sqrt n，这样，枚举\sqrt n个数，以\sqrt n的复杂度判断每个数是否合规，基本上就美滋滋的可以AC了。
但是，还有一招，如果k是个合数，必有k=a \cdot b,a>1,b>1那么，x= k \cdot d =a \cdot b \cdot d，而a \cdot d > d。这说明，k是素数，题目可以等价为满足k且k的素数的数量。那么就很好办了，由于k<\sqrt n只要事先枚举10^5以内的素数，到时候二分查找一下，就可以以log( \sqrt n)的复杂度轻松AC了。