【BZOJ 2721】 樱花
2024-09-07 17:38:30
【题目链接】
【算法】
令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 ; }
最新文章
- 如何使用UltraCompare对比两个文件夹内容差异
- Python中如何读取xls中的数据
- Spring-Context之一:一个简单的例子
- Nginx + Tomcat 配置
- JS正则实例
- 信号量 <;第六篇>;
- swift 中Value Type VS Class Type
- python实现简单排序算法
- java开发中几种常见的线程池
- AngularJs的基本使用(一)
- 面试题int和Integer
- Pytorch学习(一)基础语法篇
- JavaScript之12306自动刷新车票[待完善]
- 自学Java第四周的总结
- Python学习笔记第三周
- kmp小记
- BZOJ.3058.四叶草魔杖(Kruskal 状压DP)
- 将struts的jar包拷贝到WEB-INF/lib导致eclipse中配置好的javadoc失效
- 母版页 VS shtml&mdash;ASP.NET细枝末节(3)
- Html中的次方符号怎么写