「BZOJ2721」「LuoguP1445」 [Violet]樱花（数论

题目背景

我很愤怒

题目描述

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

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

输入输出格式

输入格式：

输入一个整数N

输出格式：

输出答案

输入输出样例

输入样例#1：复制

输出样例#1：复制

102426508

题解

看到原题面的我也很愤怒。

显然是道数论题，所以我们要去分析它的性质。

$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$

$\frac{x+y}{x*y}=\frac{1}{n!}$

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

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

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

设$t=(n!)$

$(x-t)*(y-t)=t^2$

∵$x,y$是正整数，∴$x-t>0$且$y-t>0$

（若要小于0，则$(x-t)$和$(y-t)$中至少要有一个小于$-t$，也就是$x<0$或$y<0$，与题设不符

设$A=(x-t)$，$B=(y-t)$

则有$A*B=t^2=(n!)^2$

所以$A$的方案数就是$(n!)^2$的因子数，也就是一些质因子乘起来的结果。

所以把$(n!)^2$分解质因数，设为$(n!)^2={a_1}^{p_1}*{a_2}^{p_2}...*{a_m}^{p_m}$

则答案为$(p_1+1)*(p_2+1)*...*(p_m+1)$。

  qwerta

 P1445 [Violet]樱花 Accepted 

 代码 C++，.54KB

 提交时间 -- ::

 耗时/内存 86ms, 2692KB

 #include<iostream>

 #include<cstdio>

 using namespace std;

 bool sf[];

 int p[];

 int main()

 {

     int n;

     scanf("%d",&n);

     int tos=;

     for(int i=;i<=n;++i)

     if(!sf[i])

     {

         p[++tos]=;//因为是(n!)的平方，所以次数+=2

         for(int j=;i*j<=n;++j)

         {

             int x=i*j;

             sf[x]=;

             while(x%i==)

             {

                 p[tos]+=;

                 x/=i;

             }

         }

     }

     /*

     for(int i=2;i<=n;++i)

     {

         int x=i;

         for(int j=1;j<=tos&&x>1;++j)

         {

             while(x%st[j]==0)

             {

                 p[j]+=2;

                 x/=st[j];

             }

         }

     }

     */注释掉的是暴力分解2~n的质因数，亲测T上天

     long long ans=,mod=1e9+;

     for(int i=;i<=tos;++i)

     ans=(ans*(p[i]+))%mod;//统计答案

     cout<<ans;

     return ;

 }

巴特西

「BZOJ2721」「LuoguP1445」 [Violet]樱花（数论

题目背景

题目描述

输入输出格式

输入输出样例

题解

最新文章

热门文章