【POJ2992】Divisors
2024-09-03 03:52:03
【题目概括】
计算\(C_n^k\)的因子个数。
【思路要点】
- 首先考虑将组合数展开,展开后就是\(\frac {n!}{k!\times (n-k)!}\)。
- 这样就是计算出这些质因子的个数,然后将插值相乘就是答案了。
- 但是数据较大,所以我们考虑一开始先将所有答案预处理来。
- 如果是暴力求解,那么就会超时。
- 我们考虑用归纳法来计算,如果计算出\(C_{n}^{k}\),那么如何计算出\(C_n^{k+1}\)。
- 那么将式子展开,就相差了\(k+1\)和\(n-k+1\),就\(O(n)\)计算一次。
- 时间复杂度 \(\mathcal O(n^3)\)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 505;
int x, y, primeCnt;
bool ntPrime[N];
ll tot[N];
int prime[N];
ll ans[N][N];
void getPrime(int lim) {
for (int i = 2; i <= lim; i++) {
if (!ntPrime[i])
prime[++primeCnt] = i;
for (int j = 1; j <= primeCnt && i * prime[j] <= lim; j++) {
ntPrime[i * prime[j]] = 1;
if (i % prime[j])
break;
}
}
}
void divide(int x, int tp) {
for (int i = 1, cnt; i <= primeCnt; i++) {
if (x % prime[i] == 0) {
cnt = 0;
while (x % prime[i] == 0) {
x /= prime[i];
cnt++;
}
tot[i] += tp * cnt;
}
}
}
ll solve(int x, int y) {
for (int i = x; i >= (x - y + 1); i--)
divide(i, 1);
for (int i = 1; i <= y; i++)
divide(i, -1);
ll ans = 1;
for (int i = 1; i <= primeCnt; i++)
ans *= tot[i] + 1;
return ans;
}
void init() {
for (int i = 0; i <= 432; i++)
for (int j = 0; j <= 432; j++)
ans[i][j] = 1ll;
for (int i = 1; i <= 432; i++) {
memset(tot, 0, sizeof tot);
ans[i][1] = solve(i, 1);
for (int j = 2; j <= (i >> 1); j++) {
divide(j, -1);
divide(i - j + 1, 1);
for (int k = 1; k <= primeCnt; k++)
ans[i][j] *= tot[k] + 1;
}
}
}
int main() {
getPrime(450);
init();
while (scanf("%d %d", &x, &y) != EOF) {
y = min(y, x - y);
printf("%lld\n", ans[x][y]);
}
return 0;
}
最新文章
- gulp教程之gulp-htmlmin
- Android工作学习第5天之Activity的完全退出程序
- 【动态规划】bzoj1663 [Usaco2006 Open]赶集
- spring.net (3)依赖注入基础
- 蓝牙的SDP协议总结
- 异步非阻塞IO的Python Web框架--Tornado
- Struts2学习笔记--Struts例子及开发流程
- BZOJ 4016: [FJOI2014]最短路径树问题( 最短路 + 点分治 )
- Java服务器下载速度的限制
- java web面试
- nginx中支持.htaccess并禁止php在特定目录无法运行
- JavaScript开发工具简明历史
- docker 系列 - 修改容器的 DNS 服务器
- 删除元素splice、shift\pop
- Zookeeper安装使用
- spring mvc controller中的参数验证机制(二)
- Sublime Text3—常用插件Emmet
- 最新版 INSPINIA IN+ - WebApp Admin Theme v2.7.1,包含asp.net MVC5示例代码,做管理系统最佳的选择。
- CPU、OpenGL/DirectorX、显卡驱动和GPU之间的关系
- CodeForces 1105E
热门文章
- shell脚本一键部署nginx
- Spring(二)--Spring入门案例
- k路归并
- 五、WebSocket 链接
- RHEL6本地YUM源配置
- tensorflow中张量_常量_变量_占位符
- Educational Codeforces Round 42 (Rated for Div. 2) E. Byteland, Berland and Disputed Cities(贪心)
- C#基础知识之图解TCP IP》读书笔记
- axios获取响应头
- day_04 基本数据类型的结构和使用方法