我们现在需要选择一个 $k$，使得 $[1,x]$ 含有的 $k$ 的个数严格小于 $[1,n]$ 含有的 $k$ 的个数。换句话说，我们需要选择一个 $k\leq m$ 满足 $\displaystyle k\mid\frac{n!}{x!}$，且 $[1,x]$ 中含有的 $k$ 需要尽可能少。
用构造题的思路，我们想一些简单情况。不难发现：如果 $(x,n]$ 中有一个质数，那么直接取这个质数，可以直接获得 $0$ 的贡献，非常优。
然后我们打一个表。发现 $[1,10^7]$ 内相邻的两个质数的最大差距不超过 $154$。所以我们找到 $\leq n$ 的最大质数 $p$，直接取 $k=p$ 即可。我们就只需要额外处理 $x\in[p,n)$ 的情况，其中 $x$ 的取值个数不超过 $k_0=154$。
$\rm Observation2$：$k$ 取一个质数的若干次幂必然不劣（根据出题人给的提示可以发现，若一个合数可以区分开 $a,b$，一定可以用这个合数的某个质因子的若干次幂区分开它们）。
然后我们再毛估估一下 $[p,n)$ 内所有数分解后本质不同质数的个数，发现也就不超过 $k_1=30$ 个。
考虑一个质数 $p$ 的贡献。记 $[1,n]$ 中有 $p[1,n]$ 个 $p$，$[1,x]$ 中有 $p[1,x]$ 个 $p$，那么我们需要找到一个最大的 $e$，满足 $p^e\leq m$，且 $\displaystyle\lfloor\frac{p[1,x]}{e}\rfloor<\lfloor\frac{p[1,n]}{e}\rfloor$。注意到由于 $p^e\leq m$ 的存在，我们可以直接倒序枚举 $O(\log n)$ 个 $e$，然后 $O(\log n)$ 计算 $p[1,x],p[1,n]$ 比较，然后就可以求得 $w(x,n)$。我们一共需要对 $k_0$ 个数计算 $k_1$ 个质数的贡献，每个质数造成复杂度 $O(\log^2n)$。总计下来，复杂度 $O(tk_0k_1\log^2n)$。取 $t,k_0$ 同阶，$k_1,\log n$ 同阶，不超过 $10^8$，可以通过，而且 $e$ 不用枚举到底，运行次数远小于上界。可以很轻松地通过。
::::success[Code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 10000005
int notp[MAXN],prime[MAXN],minp[MAXN],ptot = 0;
inline void Euler(){
notp[1] = 1;
for( int i = 2 ; i < MAXN ; i ++ ){
if( !notp[i] ) prime[++ptot] = i;
for( int j = 1 ; j <= ptot && i * prime[j] < MAXN ; j ++ ){
notp[i * prime[j]] = 1,minp[i * prime[j]] = prime[j];
if( i % prime[j] == 0 ) break;
}
}
}
int n,m,Min[MAXN];
set<int> S;
inline void Get_Cprs( int x ){
while( x > 1 ){
if( notp[x] ){
int p = minp[x];
S.insert( p );
while( x % p == 0 ) x /= p;
}
else{ S.insert( x ); return; }
}
}
inline int calc( int x , int p ){
int res = 0;
while( x ){ res += x / p,x /= p; }
return res;
}
inline void solve(){
scanf("%lld%lld",&n,&m);
int p = n; while( notp[p] ) p --;
for( int x = p ; x <= n ; x ++ ) Get_Cprs( x );
for( int x = p ; x < n ; x ++ ) Min[x] = (int)1e8;
int Ans = 0;
for( int ele : S ){
int maxe = 0,tmp = 1; while( tmp * ele <= m ) tmp *= ele,maxe ++;
for( int x = n - 1 ; x >= p ; x -- ){
int hasx = calc( x , ele ),hasn = calc( n , ele );
for( int e = maxe ; e ; e -- )
if( hasx / e < hasn / e ) Min[x] = min( Min[x] , hasx / e );
}
}
for( int x = p ; x < n ; x ++ ) Ans += Min[x];
printf("%lld\n",Ans);
S.clear();
}
signed main(){
Euler();
int testcase; scanf("%lld",&testcase);
while( testcase -- ) solve();
return 0;
}
```
::::