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;
}