思路推導

我們先對 $32$ 和 $96$ 進行二進制拆分。

相同部分（用 $\alpha$ 表示）：$5$ 個 $2$。

不同部分（用 $\beta$ 表示）：$1$ 和 $3$。

$\gcd (32,96)$ 就等于 $\alpha$，即 $32$。

$\mathrm{lcm}(32,96)=\alpha \times \beta$，即 $96$。

根據常識，兩個數字相乘不可能為質數，除非是 $1$ 乘上一個質數。

也就是說，$b$ 是 $a$ 的倍數，且 $\frac{b}{a}$ 是一個質數。

歐拉篩或埃氏篩找出 $[1,10^7]$ 范圍內的所有質數，隨后枚舉 $1$ 到 $n$，記作 $a$。

對于每一個 $a$，枚舉每個質數 $x_i$，如果 $x_i\times a>n$，那么退出本次循環，否則累加答案。

優化

可以發現，對于每個 $a$，可以直接推算出它對答案的貢獻。

二分查找，找出質數中第一個大于 $?\frac{n}{a}?$ 的位置 $p$，它對答案的貢獻為 $p?1$。

實現

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n,cnt,prime[10000005];
bool vis[10000005];
void ct(){vis[0]=vis[1]=true;for(int i=2;i<=10000000;i++){if(!vis[i]){prime[++cnt]=i;}for(int j=1;j<=cnt&&i*prime[j]<=10000000;j++){vis[i*prime[j]]=true;if(!(i%prime[j])){break;}}}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ct();for(cin>>t;t;t--){cin>>n;int ans=0;for(int i=1;i<=n;i++){ans+=upper_bound(prime+1,prime+cnt+1,n/i)-prime-1;}cout<<ans<<'\n';}return 0;
}