题解：洛谷 CF2091E Interesting Ratio

思路推导

我们先对 $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$，可以直接推算出它对答案的贡献。

二分查找，找出质数中第一个大于 $\lfloor \frac{n}{a}\rfloor$ 的位置 $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;
}