LightOJ1341 Aladdin and the Flying Carpet 题解

题目链接：Aladdin and the Flying Carpet

题意：

\(Q\) 组询问，每组询问给定 \(n,m\) ，求有多少个无序对 \((a,b)\) 满足 \[ a \times b = n \,\land\, a,b \ge m \] \(1 \le m\le n \le 10^{12}\)

关键词：因数枚举

很简单，枚举 \(n\) 的全部因数然后判断即可，直接暴力做是 \(\mathcal{O}(Q\sqrt{n})\) 的。

可以用 \(\mathtt{Pollard\ Rho}\) 算法优化到期望 \(\mathcal{O}(Qn^{\frac{1}{4}})\)

但是没必要这么麻烦，考虑一种预处理的方法。

我们可以将 \(n\) 写成唯一分解的形式，即 \(n = p_1^{t_1}p_2^{t_2}\cdots p_k^{t_k}\)

这里素因子可以用线性筛预处理，复杂度为 \(\mathcal{O}(\sqrt{N})\) 。

显然 \(n\) 的因数 \(k\) 也可以写成 \(k = p_1^{c_1}\,p_2^{c_2}\,\cdots\, p_k^{c_k}\) 的形式，其中 \(0 \le c_i \le t_i\) 。

考虑用 \(\mathtt{dfs}\) 枚举 \(c_i\) ，这样我们就能枚举出 \(n\) 所有的因数了，注意要在分解 \(n\) 的时候预处理一下。

时间复杂度 \(\mathcal{O}\left(\sqrt{N} + Q\left(\frac{2\sqrt{n}}{\ln n} + d(n)\right)\right)\)

空间复杂度 \(\mathcal{O}\left(\sqrt{N} + \omega(N)\log N\right)\)

其中 \(d(n)\) 表示 \(n\) 的因数个数，\(\omega(n)\) 表示 \(n\) 的不同素因子个数。数量级详见 link

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6+15))
#define M ((int)(1e4+15))

bitset<N> ck;
int n,m,res,tot,cnt,p[N],q[M],pwd[25][41];
void init()
{
    for(int i=2; i<=N-5; i++)
    {
        if(!ck[i]) p[++tot] = i;
        for(int j=1; j<=tot && i * p[j] <= N-5; j++)
        { ck[i * p[j]] = 1; if(i % p[j] == 0) break;} 
    }
}
void dfs(int u,int x)
{
    if(u == cnt + 1)
    {
        res += (min(x,n/x) >= m);
        // cout << x << ' ' << n/x << '\n';
        return ;
    }
    for(int i=0; i<=q[u]; i++) dfs(u+1,x*pwd[u][i]);
}
int solve()
{
    cin >> n >> m; int sq = sqrt(n); cnt = res = 0;
    if(m * m > n) return 0; int tmp = n; 
    for(int i=1; i<=tot && p[i] <= n/p[i]; i++)
        if(n % p[i] == 0)
        {
            q[++cnt]=0; pwd[cnt][0] = 1;
            for(int t; n % p[i] == 0; )
            {
                t = ++q[cnt];
                n/=p[i], pwd[cnt][t] = pwd[cnt][t-1] * p[i];
            } 
        }
    if(n > 1) { q[++cnt] = 1; pwd[cnt][0] = 1; pwd[cnt][1] = n; }
    n = tmp; dfs(1,1); return res/2;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q; init();
    for(int i=1; i<=Q; i++)
    { cout << "Case " << i << ": " << solve() << '\n'; }
    return 0;
}