当前位置:网站首页>AcWing 1294.樱花 题解
AcWing 1294.樱花 题解
2022-07-06 09:14:00 【爱吃章鱼的怪兽】
AcWing 1294.樱花 题解
题目描述
给定一个整数 n n n ,求有多少正整数对 ( x , y ) (x,y) (x,y) 满足 1 x + 1 y = 1 n ! \dfrac{1}{x}+\dfrac{1}{y}=\dfrac{1}{n!} x1+y1=n!1
输入格式:
一个整数 n n n
输出格式:
一个整数,表示满足条件的数对数量
答案对 1 0 9 + 7 10^9+7 109+7 取模
数据范围
1 ≤ n ≤ 1 0 6 1\le n \le 10^6 1≤n≤106
题解
观察式子,容易推出 x > n ! x > n! x>n! y > n ! y >n! y>n!
两个未知量 x , y x,y x,y, 知道其中一个后就能够推出另外一个
因此我们不妨设 y = n ! + k y=n!+k y=n!+k
变换后的式子为
1 x + 1 n ! + k = 1 n ! \dfrac{1}{x}+\dfrac{1}{n!+k}=\dfrac{1}{n!} x1+n!+k1=n!1
将式子两边通分可得 n ! ( n ! + k ) + ( n ! ) x = x ( n ! + k ) n!(n!+k)+(n!)x=x(n!+k) n!(n!+k)+(n!)x=x(n!+k)
变换可得
x = n ! ( n ! + k ) k = ( n ! ) 2 k + n ! x=\dfrac{n!(n!+k)}{k}=\dfrac{(n!)^2}{k}+n! x=kn!(n!+k)=k(n!)2+n!
由于x要满足正整数这一特性,所以问题转换成了k的值需要变成 ( n ! ) 2 (n!)^2 (n!)2的约数
问题变成了求一个数的约数
求约数可以用 算数基本定理
算术基本定理如下
任何一个正整数都可以用它的质因子唯一确定(其中 p i p_i pi为其质因子)
x = p 1 α 1 ⋅ p 2 α 2 ⋅ p 3 α 3 … ⋅ p n α n x=p_1^{\alpha_1} · p_2^{\alpha_2}·p_3^{\alpha_3}\dots·p_n^{\alpha_n} x=p1α1⋅p2α2⋅p3α3…⋅pnαn
根据全排列公式则其因子个数为
( α 1 + 1 ) ⋅ ( α 2 + 1 ) ⋅ ( α 2 + 1 ) ⋅ ( α 2 + 1 ) (\alpha_1+1)·(\alpha_2+1)·(\alpha_2+1)·(\alpha_2+1) (α1+1)⋅(α2+1)⋅(α2+1)⋅(α2+1)
问题变成了求解 ( n ! ) 2 (n!)^2 (n!)2的质因子和每个质因子的阶数
我们可以先求 ( n ! ) (n!) (n!)的质因子和每个质因子的阶数后将阶数乘2就可以的到 ( n ! ) 2 (n!)^2 (n!)2的解
如何求 ( n ! ) (n!) (n!)的质因子和质因子的阶数可以参考我的另一篇博客
求得 ( n ! ) (n!) (n!)的所有质因子后将质因子的阶数乘2,最后利用因子个数的计算公式就可以得到k的所有取值
对于每一个k值都有一个x值与其对应,则最后的所有取值即为正整数数对的个数
完整代码
import java.io.*;
import java.util.*;
public class Main {
static int n;
static final int N=1000010;
static final long MOD=1000000007;
static int[] Primes =new int[N];
static boolean[] isPrime =new boolean[N];
static int cnt=0;
static long ans=1;
public static void init(int n)//线性筛
{
Arrays.fill(isPrime,true);
for(int i=2;i<=n;i++) {
if (isPrime[i])
Primes[cnt++] = i;
for(int j=0;j<cnt;j++)
{
int p=Primes[j];
if(i*p>n)
break;
isPrime[i*p]=false;
if(i%p==0)
{
break;
}
}
}
}
public static void main(String[] agrs) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
n=Integer.parseInt(reader.readLine());
init(n);
for(int i=0;i<cnt;i++)//分解质因子
{
int tmp=n;
int p=Primes[i];
long res=0;
while(tmp>0)
{
res+=tmp/p;
tmp/=p;
}
res*=2;//转换成平方的质因子阶数
ans=(ans%MOD)*((res+1)%MOD);//因子计算公式
ans%=MOD;
}
System.out.println(ans);
}
}
边栏推荐
- [BMZCTF-pwn] 12-csaw-ctf-2016-quals hungman
- Did you forget to register or load this tag 报错解决方法
- npm一个错误 npm ERR code ENOENT npm ERR syscall open
- 图片上色项目 —— Deoldify
- One click extraction of tables in PDF
- 01项目需求分析 (点餐系统)
- QT creator specifies dependencies
- Valentine's Day is coming, are you still worried about eating dog food? Teach you to make a confession wall hand in hand. Express your love to the person you want
- Some notes of MySQL
- Have you mastered the correct posture of golden three silver four job hopping?
猜你喜欢
Swagger, Yapi interface management service_ SE
Knowledge Q & A based on Apache Jena
Install mysql5.5 and mysql8.0 under windows at the same time
[recommended by bloggers] C MVC list realizes the function of adding, deleting, modifying, checking, importing and exporting curves (with source code)
A trip to Macao - > see the world from a non line city to Macao
【博主推荐】SSM框架的后台管理系统(附源码)
Mysql22 logical architecture
PyCharm中无法调用numpy,报错ModuleNotFoundError: No module named ‘numpy‘
La table d'exportation Navicat génère un fichier PDM
35 is not a stumbling block in the career of programmers
随机推荐
基于apache-jena的知识问答
【博主推荐】C# Winform定时发送邮箱(附源码)
API learning of OpenGL (2003) gl_ TEXTURE_ WRAP_ S GL_ TEXTURE_ WRAP_ T
Data dictionary in C #
Ansible practical Series II_ Getting started with Playbook
Mysql22 logical architecture
Armv8-a programming guide MMU (2)
报错解决 —— io.UnsupportedOperation: can‘t do nonzero end-relative seeks
打开浏览器的同时会在主页外同时打开芒果TV,抖音等网站
Record a problem of raspberry pie DNS resolution failure
[BMZCTF-pwn] 12-csaw-ctf-2016-quals hungman
Use dapr to shorten software development cycle and improve production efficiency
Introduction to the easy copy module
【博主推荐】SSM框架的后台管理系统(附源码)
【博主推荐】C#MVC列表实现增删改查导入导出曲线功能(附源码)
[download app for free]ineukernel OCR image data recognition and acquisition principle and product application
01项目需求分析 (点餐系统)
Ansible practical Series III_ Task common commands
数数字游戏
Deoldify项目问题——OMP:Error#15:Initializing libiomp5md.dll,but found libiomp5md.dll already initialized.