51nod 1189 阶乘分数(数论)

简介: 51nod 1189 阶乘分数(数论)

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。

输入

输入一个数N(1 <= N <= 1000000)。

输出

输出解的数量Mod 10^9 + 7。

输入样例

2

输出样例

2


1/N! = 1/X + 1/Y

=> 1/N! = (X+Y)/XY

=> XY = N!(X+Y)

=> (X-N!)(Y-N!) = (N!)^2

A*B = (N!)^2

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2000005;
typedef long long ll;
const int mod = 1e9 + 7;
int prime[maxn];
int isprime[maxn];
int cnt = 0;
ll base = 500000004;
void getPrime(int n) {
  isprime[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!isprime[i]) {
      prime[++cnt] = i;
    }
    for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
      isprime[i * prime[j]] = 1;
      if (i % prime[j] == 0) {
        break;
      }
    }
  }
}
ll getCount(int x, int n) {
  ll ans = 0;
  while (n) {
    ans += n / x;
    n /= x;
  }
  return ans;
}
int main() {
  int n;
  cin >> n;
  getPrime(n);
  ll ans = 1;
  for (int i = 1; i <= cnt; i++) {
    ll x = getCount(prime[i], n) * 2% mod;
    ans = ans * (x + 1)% mod;
  }
  cout << (ans + 1) * base % mod<< endl;
  return 0;
}
目录
打赏
0
0
0
0
0
分享
相关文章
Helm3部署Rancher2.6.3高可用集群
Helm3部署Rancher2.6.3高可用集群,通过创建 Kubernetes Secret 使用自签证书。
486 1
分布式系统架构2:服务发现
服务发现是分布式系统中服务实例动态注册和发现机制,确保服务间通信。主要由注册中心和服务消费者组成,支持客户端和服务端两种发现模式。注册中心需具备高可用性,常用框架有Eureka、Zookeeper、Consul等。服务注册方式包括主动注册和被动注册,核心流程涵盖服务注册、心跳检测、服务发现、服务调用和注销。
337 13
加码香港!连续市场第一,启动新计划
加码香港!连续市场第一,启动新计划
199 4
ElasticSearch的简单介绍与使用【入门篇】
这篇文章是Elasticsearch的入门介绍,涵盖了Elasticsearch的基本概念、特点、安装方法以及如何进行基本的数据操作,包括索引文档、查询、更新、删除和使用bulk API进行批量操作。
ElasticSearch的简单介绍与使用【入门篇】
大数据-91 Spark 集群 RDD 编程-高阶 RDD广播变量 RDD累加器 Spark程序优化
大数据-91 Spark 集群 RDD 编程-高阶 RDD广播变量 RDD累加器 Spark程序优化
131 0
拯救php性能的神器webman-数据库
Webman 框架与这些最佳数据库管理实践的结合,可为应用程序提供快速响应的用户体验,高吞吐量,提升应用程序的整体性能表现。在对数据库交互进行设计和开发时,持续关注性能指标和优化,确保数据库层面不会成为应用程序的瓶颈,这样便能充分利用 Webman 来提升 PHP 应用的性能。
325 4
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问