题目分析

$x=1$只能贡献一个 $1$，将它扔掉。

什么情况下会出现 $x_1^{y_1}=x_2^{y_2}$呢？

当 $x_1=r^{y_2}$，$x_2=r^{y_1}$时。

于是我们可以将所有大于等于 $2$小于等于 $A$数分组，第 $i$组是所有 $i$的幂（$i$不能被表示为其他数的幂）。

如 $A=37$时，前几组是：$S_2={ 2,4,8,16,32 },S_3={ 3,9,27 },S_5={ 5,25 }$

每组的元素个数最多是30个。注意到当 $i > \sqrt{A}$时，$i$要么是其他数的幂，要么贡献一个大小为 1 的组。所以我们暴力扫一次 $\sqrt{A}$内的部分，可以得到每个大小的组有多少个。

对于一个大小为 $t$的组，考虑一个子问题：当 $x \leq t$，$y \leq B$时，有多少种不同的 $xy$？

我们将 $[1,tB]$上的数分成 $t$段，第 $i$段为 $[(i-1)B+1,iB]$。然后对每段单独考虑贡献。

对于第 $i$段，显然有 $x \in [i,t]$，并且该段中任何一个可以写成满足取值范围的 $x$的倍数的数，都是可以写作合法的 $xy$的数。

对于所有取值范围内的 $x$进行容斥，可以得到这样的数有多少个。

但是 $x$最多有 $30$个，容斥的复杂度是 $2^{t-i+1}$的。于是我们将所有可以写成区间内其他一个 $x$的倍数的 $x$全部删掉，这样最多剩下 $15$个数，复杂度就不会爆炸了。

求一个子集内的数的 LCM 时，要用一点小 trick：求该子集删掉一个数后的子集的 LCM 和这个数的 LCM。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef long long LL;
LL ans,A,B;
int ban[32000],sz[32780],Log[32780];LL cnt[30],lcm[32780],d[30];

#define bin(x) (1<<(x))
#define lowbit(x) ((x)&(-(x)))
LL gcd(LL x,LL y) {return y?gcd(y,x%y):x;}
LL getlcm(LL x,LL y) {return x*y/gcd(x,y);}
LL work2(LL L,LL R,int js) {
    LL re=0;lcm[0]=1;
    for(RI zt=1;zt<bin(js);++zt) {
        lcm[zt]=getlcm(lcm[zt^lowbit(zt)],d[Log[lowbit(zt)]+1]);
        if(sz[zt]&1) re+=R/lcm[zt]-L/lcm[zt];
        else re-=R/lcm[zt]-L/lcm[zt];
    }
    return re;
}
LL work1(int t) {
    LL re=0;
    for(RI i=1;i<=t;++i) {
        LL L=1LL*(i-1)*B,R=1LL*i*B;int js=0;
        for(RI j=i;j<=t;++j) ban[j]=0;
        for(RI j=i;j<=t;++j) {
            if(ban[j]) continue;
            d[++js]=j;
            for(RI k=j;k<=t;k+=j) ban[k]=1;
        }
        re+=work2(L,R,js);
    }
    return re;
}
class ThePowers{
    public:
    LL find(int kA,int kB) {
        A=kA,B=kB,ans=1,cnt[1]=A-1;
        for(LL i=2;i*i<=A;++i) {
            if(ban[i]) continue;
            int js=0;
            for(LL j=i;j<=A;j*=i,++js) if(j*j<=A) ban[j]=1;
            cnt[1]-=js,++cnt[js];
        }
        for(RI i=0;i<15;++i) Log[bin(i)]=i;
        for(RI zt=0;zt<bin(15);++zt) sz[zt]=sz[zt>>1]+(zt&1);
        for(RI i=1;i<=29;++i) if(cnt[i]) ans+=cnt[i]*work1(i);
        return ans;
    }
};