数论 HDOJ 5407 CRB and Candies
2024-08-30 19:07:32
题意:求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;
}
最新文章
- Erlang环境用eclipse搭建
- Ubuntu 14.04 载入 JWS 或 访问 jsp异常的解决方法
- VBA的一些使用心得
- hdu 3537 Daizhenyang&#39;s Coin (翻硬币游戏)
- 使用Boost asio实现异步的TCP/IP通信
- django TypeError: &#39;module&#39; object is not callable
- uploadify 配置后,页面显示无效果
- python_day06(ip代理池)
- 模拟stringBeanFactory解析xml
- css3兼容360
- HTML入门14
- Python--Virtualenv简明教程(转载https://www.jianshu.com/p/08c657bd34f1)
- java_自定义标签运行原理
- svn文件夹解锁批处理
- Java正则解析HTML一例
- COFF,amd64.vc90.mfc两个布署的问题
- linux终端发送邮件
- Mac Apache Maven 配置
- BZOJ 2720: [Violet 5]列队春游
- 科学计算三维可视化---Mayavi入门(Mayavi介绍和安装)
热门文章
- java native interface JNI 调用Java方法
- 3.将maven项目jar纳入maven仓库,Mave项目依赖另外一个Maven项目的案例
- Android中的动画具体解释系列【2】——飞舞的蝴蝶
- android &;lt;application&;gt; 开发文档翻译
- 24Web前端架构
- Android中View窗口getWidth和getMeasuredWidth的差别
- input from 表单提交 使用 属性 disabled=&;quot;disabled&;quot; 后台接收不到name=&;quot;username&;quot;的值
- IO流-获取指定目录下文件夹和文件对象【File类】
- python 2.*和3.*的变化
- Python标准库:内置函数complex([real[, imag]])