【题目链接】

点击打开链接

【算法】

令n!=z,因为1 / x + 1 / y = 1 / z,所以x,y>z,不妨令y = z + d

则1 / x + 1 / (z + d) = 1 / z

1 / x = 1 / z - 1 / (z + d)

1 / x = d / (z + d)z

x = z(z + d) / d = z^2 / d + z

因为x是正整数,所以z^2 / d是正整数,所以d | z^2

问题就转化为了求z^2的约数个数

约数个数定理 x = p1^k1p2^k2....pn^kn,(p1,p2,....pn)为质数,x的约数个数为(k1+1)(k2+1)...(kn+1)

分解质因数即可

【代码】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6;
const int MOD = 1e9 + ; ll N,i,k,ans=,tot=;
ll prime[MAXN+],f[MAXN+],sum[MAXN+]; template <typename T> inline void read(T &x) {
ll f=; x=;
char c = getchar();
for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }
for (; isdigit(c); c = getchar()) x = x * + c - '';
x *= f;
} template <typename T> inline void write(T x) {
if (x < ) { putchar('-'); x = -x; }
if (x > ) write(x/);
putchar(x%+'');
} template <typename T> inline void writeln(T x) {
write(x);
puts("");
} inline void sieve(ll n) {
ll i,j,tmp;
for (i = ; i <= n; i++) {
if (!f[i]) prime[++tot] = f[i] = i;
for (j = ; j <= tot; j++) {
tmp = i * prime[j];
if (tmp > n) break;
f[tmp] = prime[j];
if (f[i] == prime[j]) break;
}
}
} inline void calc(ll x) {
while (x != ) {
sum[f[x]]++;
x /= f[x];
}
} int main() { read(N);
sieve(N);
for (i = ; i <= N; i++) calc(i);
for (i = ; i <= tot; i++) ans = ans * ( * sum[prime[i]] + ) % MOD;
writeln(ans); return ; }

最新文章

  1. 如何使用UltraCompare对比两个文件夹内容差异
  2. Python中如何读取xls中的数据
  3. Spring-Context之一:一个简单的例子
  4. Nginx + Tomcat 配置
  5. JS正则实例
  6. 信号量 &lt;第六篇&gt;
  7. swift 中Value Type VS Class Type
  8. python实现简单排序算法
  9. java开发中几种常见的线程池
  10. AngularJs的基本使用(一)
  11. 面试题int和Integer
  12. Pytorch学习(一)基础语法篇
  13. JavaScript之12306自动刷新车票[待完善]
  14. 自学Java第四周的总结
  15. Python学习笔记第三周
  16. kmp小记
  17. BZOJ.3058.四叶草魔杖(Kruskal 状压DP)
  18. 将struts的jar包拷贝到WEB-INF/lib导致eclipse中配置好的javadoc失效
  19. 母版页 VS shtml&mdash;ASP.NET细枝末节(3)
  20. Html中的次方符号怎么写

热门文章

  1. Codeforces Round #320 (Div. 2) [Bayan Thanks-Round]
  2. HDU_4770 Lights Against Dudely 状压+剪枝
  3. Hadoop三种模的安装配置过程
  4. lamp安装手稿
  5. BUPT复试专题—最值问题(2013计院)
  6. NSArray中存的是实体时的排序
  7. 【转载】.NET Remoting学习笔记(三)信道
  8. 整理对Spark SQL的理解
  9. OTT
  10. HDU 1248 寒冰王座 (水题的N种做法!)(含完全背包)