LUOGU1445——没占到1444的愤怒数学

83 阅读 0 评论 55 点赞

我是靠谱客的博主爱撒娇电话，这篇文章主要介绍LUOGU1445——没占到1444的愤怒数学，现在分享给大家，希望可以做个参考。

1445

题意:给定n，求1/x+1/y=1/n!的正整数解的数量

先对原式分解一下

(x+y)/xy=1/n!

xy-(x+y)*n!=0

(n!)^2+xy-(x+y)*n!=(n!)^2

(x-n!)*(y-n!)=(n!)^2

因为x,y为任意正整数，所以x-n!和y-n!也可以是任意正整数

所以题意转化为->x*y=(n!)^2

那么我们对n!分解质因数

然后我们考虑x的取值，显然，若一个质数p有k个，那么x可以取p^0,p^1....p^k

共(k+1)种情况

乘法原理乘起来就可以了

而且显然，x确定后，y必然也会被确定

CODE：

复制代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <string>
#include <map>
#include <cstring>
#include <ctime>
#include <vector>
#define inf 1e9
#define ll long long
#define For(i,j,k) for(ll i=j;i<=k;i++)
#define Dow(i,j,k) for(ll i=k;i>=j;i--)
using namespace std;
inline void read(ll &tx){   ll x=0,f=1;char ch=getchar();   while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}  while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}  tx=x*f; }
inline void write(ll x){    if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10);   putchar(x%10+'0');  }
inline void writeln(ll x){write(x);puts("");}
using namespace std;
ll n,ans,cnt[3000001],last[3000001],pri[3000001],tot;
ll mo=1e9+7;
bool bj[3000001];
inline void get_pri()
{
    For(i,2,n)
    {
        if(!bj[i]){pri[++tot]=i;last[i]=tot;}
        For(j,1,tot)
        {
            if(i*pri[j]>n)    break;
            bj[i*pri[j]]=1;
            last[i*pri[j]]=j;
            if(i%pri[j]==0)    break;
        }
    }
}
inline void fj(ll x)
{
    while(x!=1)
    {
        cnt[last[x]]++;cnt[last[x]]%=mo;
        x/=pri[last[x]];
    }
    
}
int  main()
{
    read(n);
    get_pri();
    For(i,2,n)
        fj(i);
    For(i,1,tot)    cnt[i]*=2LL,cnt[i]%=mo;
    ans=1;
    For(i,1,tot)
        ans=ans*(cnt[i]+1)%mo;
    writeln(ans);
    system("pause");
}

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <string>
#include <map>
#include <cstring>
#include <ctime>
#include <vector>
#define inf 1e9
#define ll long long
#define For(i,j,k) for(ll i=j;i<=k;i++)
#define Dow(i,j,k) for(ll i=k;i>=j;i--)
using namespace std;
inline void read(ll &tx){   ll x=0,f=1;char ch=getchar();   while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}  while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}  tx=x*f; }
inline void write(ll x){    if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10);   putchar(x%10+'0');  }
inline void writeln(ll x){write(x);puts("");}
using namespace std;
ll n,ans,cnt[3000001],last[3000001],pri[3000001],tot;
ll mo=1e9+7;
bool bj[3000001];
inline void get_pri()
{
    For(i,2,n)
    {
        if(!bj[i]){pri[++tot]=i;last[i]=tot;}
        For(j,1,tot)
        {
            if(i*pri[j]>n)    break;
            bj[i*pri[j]]=1;
            last[i*pri[j]]=j;
            if(i%pri[j]==0)    break;
        }
    }
}
inline void fj(ll x)
{
    while(x!=1)
    {
        cnt[last[x]]++;cnt[last[x]]%=mo;
        x/=pri[last[x]];
    }
    
}
int  main()
{
    read(n);
    get_pri();
    For(i,2,n)
        fj(i);
    For(i,1,tot)    cnt[i]*=2LL,cnt[i]%=mo;
    ans=1;
    For(i,1,tot)
        ans=ans*(cnt[i]+1)%mo;
    writeln(ans);
    system("pause");
}