题目描述

原题来自:HackerRank Equations

求不定方程:

1/x+1/y=1/n!

的正整数解 (x,y) 的数目。

输入格式

一个整数 n 。

输出格式

一个整数,表示有多少对 (x,y) 满足题意。答案对 1e9+7 取模。

样例

样例输入

2

样例输出

3

样例说明

共有三个数对 (x,y) 满足条件,分别是 (3,6),(4,4) 和 (6,3)。

数据范围与提示

对于 30% 的数据,n<=100;
对于全部数据,n<=1e6。

___________________________________________________________________

数论题,关键一步真的想不到!

由于题目是正整数解,所以x,y都大于n

题目很容易化为n!=xy/(x+y)

由于x,y大于n!。所以x设为n!+a,y设为n!+b。

上面的式子就可以化为(n!)^2=a*b

也就是上面的式子,a,b有多少中解!

所以,首先求出n中的质数,然后求出所有的质数在n!中出现的次数,而(n!)^2中的后的质数的个数要乘以2,让后就是求所有因数的个数。

___________________________________________________________________

 1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn=1e6;
4 int n;
5 int prime[maxn],cnt[maxn];
6 bool sz[maxn];
7 int js;
8 void getprime(int n)
9 {
10 sz[0]=sz[1]=1;
11 for(int i=2;i<=n;++i)
12 {
13 if(sz[i]==0)prime[js++]=i;
14 for(int j=0;j<js&&prime[j]*i<=n;++j)
15 {
16 sz[prime[j]*i]=1;
17 if(i%prime[j]==0)break;
18 }
19 }
20 }
21 void fenjie(int x)
22 {
23 for(int i=0;prime[i]*prime[i]<=x;++i)
24 while(x%prime[i]==0)
25 {
26 x/=prime[i];
27 cnt[prime[i]]++;
28 }
29 if(x!=1)cnt[x]++;
30 }
31 long long ans=1;
32 int main()
33 {
34 cin>>n;
35 getprime(n);
36 for(int i=2;i<=n;++i)fenjie(i);
37 for(int i=2;i<=n;++i)ans=(ans*((cnt[i]<<1)+1))%1000000007;
38 cout<<ans;
39 return 0;
40 }

最新文章

  1. Visual Studio EventHandler Delegate 和 EventArgs
  2. Sharepoint学习笔记—习题系列--70-576习题解析 -(Q49-Q51)
  3. 【原创】angularjs1.3.0源码解析之scope
  4. 二分查找or折半查找
  5. Storm Esper
  6. Swift - 使用导航条和导航条控制器来进行页面切换
  7. java:高速排序算法与冒泡排序算法
  8. Java 不使用科学计数法表示数据设置
  9. 从零开始搭建ELK+GPE监控预警系统
  10. RGB与HSV之间的转换公式及颜色表
  11. mfc动态演示排序算法
  12. 图解Raft之日志复制
  13. MVC Repository模式
  14. Builder搭建外置服务器
  15. 07-java学习-方法重载-idea集成开发工具学习-项目-模块-包
  16. Spring注解@Component、@Repository、@Service、@Controller @Resource、@Autowired、@Qualifier、@scope
  17. JVM调优常用参数
  18. PAT甲题题解-1055. The World&#39;s Richest (25)-终于遇见一个排序的不水题
  19. 撩课-Web大前端每天5道面试题-Day24
  20. Linux QT数据库之登录注册

热门文章

  1. Git全栈开发者使用指南
  2. 这篇文章告诉你MYSQLB+树具体索引数据组织明细内容
  3. MODBUS_RTU通信协议
  4. 第9章 集合处理(数组、Map、Set)
  5. idea多模块启动
  6. PHP 获取重复数组中 第二多的元素
  7. 人生苦短我用Python,本文助你快速入门
  8. 谈谈你不知道的gist
  9. Linux学习笔记 | 将默认镜像源修改为国内镜像源
  10. zabbix 监控tomcat