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月前
|
数学知识:质数与约数
数学知识:质数与约数
88 0
筛质数、分解质因数和快速幂的应用
筛质数、分解质因数和快速幂的应用
83 0
迭代法解决递推问题:数列和,sinx,ex的近似值
迭代法解决递推问题:数列和,sinx,ex的近似值
149 0
【数学】【数论】【最大公约数】1819. 序列中不同最大公约数的数目
【数学】【数论】【最大公约数】1819. 序列中不同最大公约数的数目
|
10月前
|
C++
【PTA】​ L1-080 乘法口诀数列​(C++)
【PTA】​ L1-080 乘法口诀数列​(C++)
123 0
【PTA】​ L1-080 乘法口诀数列​(C++)
【数论】试除法判断质数,分解质因数,筛质数
将定义进行模拟,若整除了除1与其自身的另外的数,则为质数
160 0
数学问题之(矩阵加速递推快速幂)
数学问题之(矩阵加速递推快速幂)
106 0
Python实现求取素数
Python实现求取素数
277 0
51nod 1711 平均数(二分 + 树状数组好题)
51nod 1711 平均数(二分 + 树状数组好题)
110 0