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
分享
相关文章
|
10月前
PTA-求平方与倒数序列的部分和
求平方与倒数序列的部分和
84 1
【数学】【数论】【最大公约数】1819. 序列中不同最大公约数的数目
【数学】【数论】【最大公约数】1819. 序列中不同最大公约数的数目
|
10月前
|
leetcode-461:汉明距离
leetcode-461:汉明距离
47 0
数学问题之(矩阵加速递推快速幂)
数学问题之(矩阵加速递推快速幂)
109 0
51nod 1711 平均数(二分 + 树状数组好题)
51nod 1711 平均数(二分 + 树状数组好题)
111 0
LeetCode 461. 汉明距离
LeetCode 461. 汉明距离
123 0
辗转相除法(既约分数)
辗转相除法(既约分数)
127 0
【AcWing】曼哈顿距离
【AcWing】曼哈顿距离
104 0
AI助理

你好,我是AI助理

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