题目传送门

题意:求LCM (C(N,0),C(N,1),...,C(N,N)),LCM是最小公倍数的意思,C函数是组合数。

分析:先上出题人的解题报告

  

  好吧,数论一点都不懂,只明白f (n + 1)意思是前n+1个数的最小公倍数,求法解释参考HDOJ 1019,2028

这个结论暂时不知道怎么推出来的,那么就是剩下1/(n+1) 逆元的求法了

代码:

/************************************************
* Author :Running_Time
* Created Time :2015-8-21 14:52:39
* File Name :B.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
ll f[N];
int p[N]; bool ok(int n) {
int t = p[n];
while (n % t == 0 && n > 1) n /= t;
return n == 1;
} void seive(int n) {
for (int i=1; i<=n; ++i) p[i] = i;
for (int i=2; i<=n; ++i) {
if (p[i] == i) {
for (int j=2*i; j<=n; j+=i) p[j] = i;
}
}
} ll pow_mod(int a, int x, int p) {
ll ret = 1;
while (x) {
if (x & 1) ret = ret * a % p;
a = a * 1ll * a % p;
x >>= 1;
}
return ret;
} ll Inv(int a) {
return pow_mod (a, MOD - 2, MOD);
} void solve(void) {
seive (1000010);
f[0] = 1;
for (int i=1; i<=1000010; ++i) {
if (ok (i)) {
f[i] = f[i-1] * p[i] % MOD;
}
else f[i] = f[i-1];
}
} int main(void) {
solve ();
int T; scanf ("%d", &T);
while (T--) {
int n; scanf ("%d", &n);
printf ("%I64d\n", f[n+1] * Inv (n + 1) % MOD);
} return 0;
}

  

最新文章

  1. Erlang环境用eclipse搭建
  2. Ubuntu 14.04 载入 JWS 或 访问 jsp异常的解决方法
  3. VBA的一些使用心得
  4. hdu 3537 Daizhenyang&#39;s Coin (翻硬币游戏)
  5. 使用Boost asio实现异步的TCP/IP通信
  6. django TypeError: &#39;module&#39; object is not callable
  7. uploadify 配置后,页面显示无效果
  8. python_day06(ip代理池)
  9. 模拟stringBeanFactory解析xml
  10. css3兼容360
  11. HTML入门14
  12. Python--Virtualenv简明教程(转载https://www.jianshu.com/p/08c657bd34f1)
  13. java_自定义标签运行原理
  14. svn文件夹解锁批处理
  15. Java正则解析HTML一例
  16. COFF,amd64.vc90.mfc两个布署的问题
  17. linux终端发送邮件
  18. Mac Apache Maven 配置
  19. BZOJ 2720: [Violet 5]列队春游
  20. 科学计算三维可视化---Mayavi入门(Mayavi介绍和安装)

热门文章

  1. java native interface JNI 调用Java方法
  2. 3.将maven项目jar纳入maven仓库,Mave项目依赖另外一个Maven项目的案例
  3. Android中的动画具体解释系列【2】——飞舞的蝴蝶
  4. android &amp;lt;application&amp;gt; 开发文档翻译
  5. 24Web前端架构
  6. Android中View窗口getWidth和getMeasuredWidth的差别
  7. input from 表单提交 使用 属性 disabled=&amp;quot;disabled&amp;quot; 后台接收不到name=&amp;quot;username&amp;quot;的值
  8. IO流-获取指定目录下文件夹和文件对象【File类】
  9. python 2.*和3.*的变化
  10. Python标准库:内置函数complex([real[, imag]])