BZOJ2721 约数定理

Posted on | In , ,

给定$n$，求有多少正整数数对 $(x,y)$ 满足 $\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}$
$(n\le 10^{6})$

题目链接

题解

  • 令 $\rm n!=z$
  • 故转化为 $\frac{1}{x} + \frac{1}{y} = \frac{1}{z}$。
  • 显然 $x,y$ 都要大于 $z$，故设 $x=z+a,y=z+b$。
  • 化简可得：$z^2=a·b$
  • 问题就转化为求 $z^2$ 的约数个数。
  • $z^2$ 的约数即为 $z$ 每个约数的 $2$ 倍。
  • 求 $[1,n]$ 每个数的约数个数，可以直接暴力预处理素数，然后算 $[1,n]$ 中素数的倍数。
  • 另外我们知道 线性筛法 每个合数只会被其最小的质数所筛掉，可以通过记录每个数的最小合数递归计算。
  • 时间复杂度 $O(n)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e6+10;
const int mod=1e9+7;

vector<int>g[maxn];
int tot, prime[maxn], rprime[maxn], ans[maxn];

int n;
bool is_prime[maxn];

void ok()
{
    is_prime[1]=true;
    tot=0;
    for(int i=2; i<=n; i++)
    {
        if(!is_prime[i]){
            prime[++tot]=i;
        }
        for(int j=1; j<=tot; j++)
        {
            if(i*prime[j]>n) break;
            is_prime[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }

    }
}


int main()
{

    scanf("%d", &n);
    ok();
    ll ans=1;
    for(int i=1;i<=tot;i++)
    {
        int now=n, cnt=0;
        while(now)
        {
            cnt+=now/prime[i];
            now/=prime[i];
        }
        cnt=(cnt<<1|1)%mod;
        ans = (ans * cnt)%mod;
    }
    printf("%lld\n", ans);
    return 0;
}