[原创]51nod 1189 阶乘分数 [因子个数+逆元]【数论】
2017-01-11 23:28:45 Tabris_ 阅读数:293
博客爬取于2020-06-14 22:42:16
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54354875
题目连接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1189
----------------------------------------------------------------------------------.
1189 阶乘分数
题目来源: Spoj
基准时间限制:1 秒 空间限制:131072 KB 分值: 80 难度:5级算法题 收藏 关注
1/N! = 1/X + 1/Y(0< x<=y),给出N,求满足条件的整数解的数量。例如:N = 2,1/2 = 1/3 + 1/6,1/2 = 1/4 + 1/4。由于数量可能很大,输出Mod 10^9 + 7。
Input
输入一个数N(1 <= N <= 1000000)。
Output
输出解的数量Mod 10^9 + 7。
Input示例
2
Output示例
2
-------------------------------------------------------------------------------------.
解题思路:
对于这种题目就是转换下式子
由于
$\frac{1}{N!}=\frac{1}{X}+\frac{1}{Y}$
$\frac{1}{X}=\frac{1}{N!}-\frac{1}{Y}$
$\frac{1}{X}=\frac{N!-Y}{YN!}$
$YN!=(N!-X)Y$
同理可得
$XN!=(N!-Y)*X$
可得
$X*N!YN!=(N!-X)Y(N!-Y)*X$
化简为
$N!N!=(N!-X)(N!-Y)$
这个时候由于N事确定的,那么将$(N!-X)$看成一个整体,那么其为$(N!)^2$的因子,$(N!-X)$有多少个X就有多少个,
Y同理.
这样的话就是求$(N!)^2$的因子个数$\prod_{i=0}^{prime-num}(1+a_i)$了.
但是由于题目要求,$X<=Y$,所以结果是$[\frac{\prod_{i=0}^{prime-num}(1+a_i)}{2}]_{向上取整}$
除2很简单,求一下逆元即可
附本题代码
# include <bits/stdc++.h> |


