题解：P10584 [蓝桥杯 2024 国 A] 数学题

· · 题解

upd on 2024.6.27:怎么给我题解撤下了，改了下之前写错的地方

题意：求所有满足 i\le n,j\le m,\sqrt{ij}\in\mathbb Z 的 (i,j) 的组数，1\le n,m\le 1.5\times 10^{16}。

做法：

考虑对于一组合法的 (i,j)，假设对于 n=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k} 定义 x_n=p_1^{a_1\bmod 2}p_2^{a_2\bmod 2}\dots p_k^{a_k\bmod 2}，那么一定有 x_i=x_j。

可以理解为 i 和 j 中所有不是平方数的部分都相同，这样乘起来之后就可以不剩任何部分的指数为奇数了。

而此时对于一个 x，所有 x_i=x 的 i 都可以写成 x\times y^2 的形式。

那我们换一个角度去计数，问题转化为求 \sum\limits_x \lfloor\sqrt\dfrac nx\rfloor\lfloor\sqrt\dfrac mx\rfloor。

后面这两个东西可以整除分块，端点数量是 O(\sqrt[3]n) 的。

此时求和中 x 的限制是形如 p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}，其中 0\le a_1,a_2,\dots,a_k\le 1。这不就是无平方因子数吗！

在进行整除分块之后，现在的问题变成了查询区间内无平方因子数的个数。

你可以按照上面那题的题解区做法，但是那样需要预处理 \sqrt n 的 \mu 函数前缀和，空间和时间都会被卡。

我们查询那题最优解，得到这样一个做法：Link。

简单来说，就是 \mu^2 的前缀和可以转化为 \sum\limits_{d^2t\le n}\mu(d)。

Dirichlet 双曲线法可以参考我找到的一篇知乎文章，下面是代入上面式子的具体推导：

假设存在 u,v，其中 v=\lfloor\dfrac n{u^2}\rfloor，则

\begin{array}{rcl} \sum\limits_{x^2y\le n}\mu(x)&=& \sum\limits_{x^2\le u^2,x^2y\le n}\mu(x)+\sum\limits_{u^2<x^2\le n,x^2y\le n}\mu(x)\\ &=&\sum\limits_{x^2\le u^2}\mu(x)\sum\limits_{y\le n/x^2}1+\sum\limits_{y\le v}1\sum\limits_{x^2\le n/y}\mu(x)-\sum\limits_{x^2\le u^2,y\le v}\mu(x)\\ &=&\sum\limits_{x\le u}\mu(x)\lfloor\dfrac n{x^2}\rfloor+\sum\limits_{y\le v}S_\mu(\sqrt\dfrac ny)-vS_\mu(u) \end{array}

取 u=v=\sqrt[3]n 即可平衡复杂度。

其它细节可以自己参考前两篇文章，因为我实际上直接硬写就过了。

实现：

ull calc2(ll n){// 计算 1~n 非平方因子数的个数
    if(n==0)return 0;
    ll T=cbrt(n);
    while((T+1)*(T+1)*(T+1)<=n)T++;
    ull ans=-calc1(T)*T;// 先算后面的部分
    for(ull i=1;i<=T;i++)ans+=Mu[i]*(n/(i*i))+calc1(SQRT(n/i));//两个同时计算，calc1 是 mu 前缀和，直接杜教筛
    return ans;
}
void __SOLVE__(ll _case){
    init(3000000);//线性筛预处理小范围的 mu 和前缀和
    cin>>n>>m;
    for(ull l=1,r,x;l<=n;l=r+1){// 计算断点
        ps.push_back(l);
        x=SQRT(n/l);
        r=n/(x*x);
    }
    for(ull l=1,r,x;l<=m;l=r+1){
        ps.push_back(l);
        x=SQRT(m/l);
        r=m/(x*x);
    }
    ps.push_back(1),ps.push_back(min(n,m)+1);
    sort(all(ps)),ps.erase(unique(all(ps)),ps.end());
    ull ans=0;
    for(int i=0;i<ps.size()-1;i++){
        ull l=ps[i],r=ps[i+1]-1;
        ans+=(calc2(r)-calc2(l-1))*(ull)(SQRT(n/l))*(ull)(SQRT(m/l));// 对于每个区间内计算答案
    }
    cout<<ans<<"\n";
}