数论好题

2721: [Violet 5]樱花

A6OCvQ.gif

简化版:

求方程 $ \dfrac{1}{X}+\dfrac{1}{Y}= \dfrac{1}{N!}$ 的正整数解的组数，其中 $ N≤10^6 $ 。

解的组数，应模$1e9+7$。

Input:

A6OSC8.gif

Output:

A6O9gg.gif

Sample Input:

$1439$

Sample Output:

$102426508$

HINT:

A6Op8S.gif

题解：

STEP1:

尝试化简该式子？

可以注意到 $X>N!$

那么可以设 $X = (N!+a)$

代入原式得:

$\dfrac{1}{N!+a}+\dfrac{1}{Y}= \dfrac{1}{N!}$

通分:

$Y×N!+N!\times(N!+a)=Y×(N!+a)$

化简:

$(N!)^2+aN!=aY$

$Y=\dfrac{(N!)^2}{a}+N!$

$a|(N!)^2$ 时$Y$为整数。

任意一个能整除$(N!)^2$的$a$可以确定一个$Y$从而确定$X$也就是该 $ \dfrac{1}{X}+\dfrac{1}{Y}= \dfrac{1}{N!}$方程的一组解。

$∴$ 答案就是$(N!)^2$的约数个数。

STEP2:

但是如何求$(N!)^2$的约数个数？

根据算数基本定理的推论：

$(c1+1)×(c_2+1)×…×(c_m+1)=\prod{i=1}^{m}(c_i+1)$

$c_i$是分解出质因数的指数。

Code

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
53
54
55
56
57
58
59
60
61
#include<cstdio>
#define ll long long
using namespace std;
inline ll read(){
    ll ans=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}
    while(ch>='0'&&ch<='9'){ans=ans*10+ch-48;ch=getchar();}
    return ans*f;
}
void write(ll x){
    if(x<0){putchar('-');x=-x;}
    if(x>9){write(x/10);}
    putchar(x%10|48);
}
const int MOD=1e9+7;
const int N=1e6;
int n;
int cnt,prime[N+5];
bool book[N+5];
inline void getprime(){
    book[1]=true;
    for (int i=2;i<=N;i++){
        if(!book[i]){
            prime[++cnt]=i;
        }
        for (int j=1;j<=cnt;j++){
            if(i*prime[j]>N){
                break;
            }
            book[i*prime[j]]=1;
            if(i%prime[j]==0){
                break;
            }
        }
    }
}
int ct[N+5];
ll ans=1;
int main(){
    n=read();
    getprime();
    for (int k=2;k<=n;k++){
        int t=k;
        for (int i=1;i<=cnt && prime[i]*prime[i]<=t;i++){
            while(t%prime[i]==0){
                ct[prime[i]]++;
                t/=prime[i];
            }
        }
        if(t>1){
            ct[t]++;
        }
    }
    for (int i=1;i<=cnt;i++){
        ct[prime[i]]*=2;
        ct[prime[i]]%=MOD;
        ans=(ans*(ct[prime[i]]+1))%MOD;
    }
    write(ans);
    return 0;
}