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;
}
相关文章
|
6月前
【每日一题Day350】LC2652倍数求和 | 数学+容斥原理
【每日一题Day350】LC2652倍数求和 | 数学+容斥原理
43 0
51nod 1711 平均数(二分 + 树状数组好题)
51nod 1711 平均数(二分 + 树状数组好题)
95 0
POJ 2689 Prime Distance (埃氏筛 区间筛)
POJ 2689 Prime Distance (埃氏筛 区间筛)
110 0
|
算法 C语言 UED
[解题报告]《算法零基础100讲》(第1讲) 幂和对数
[解题报告]《算法零基础100讲》(第1讲) 幂和对数
[解题报告]《算法零基础100讲》(第1讲) 幂和对数
|
Java
HDOJ/HDU 1250 Hat's Fibonacci(大数~斐波拉契)
HDOJ/HDU 1250 Hat's Fibonacci(大数~斐波拉契)
98 0
|
人工智能 BI 机器学习/深度学习
|
算法 大数据
51Nod 1080 两个数的平方和(数论,经典题)
1080 两个数的平方和                 基准时间限制:1 秒 空间限制:131072 KB 分值: 5         难度:1级算法题                 给出一个整数N,将N表示为2个整数i j的平方和(i
907 0