题解：洛谷 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;
}