博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
AtCoder Beginner Contest 110 D - Factorization
阅读量:6689 次
发布时间:2019-06-25

本文共 1642 字,大约阅读时间需要 5 分钟。

思路:把相同的质因子看成相同的小球,求把这些小球放进n个盒子里的方案数。

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
using namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL unsigned long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
#define pii pair
#define piii pair
#define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headconst int N = 2e5 + 10;const int MOD = 1e9 + 7;int fac[N], inv[N];int cnt[N];LL q_pow(LL n, LL k) { LL ans = 1; while(k) { if(k&1) ans = (ans * n) % MOD; n = (n * n) % MOD; k >>= 1; } return ans;}void init() { fac[0] = 1; for (int i = 1; i < N; i++) { fac[i] = (1LL * fac[i-1] * i) % MOD; } inv[N-1] = q_pow(fac[N-1], MOD-2) % MOD; for (int i = N-2; i >= 0; i--) inv[i] = (1LL * inv[i+1] * (i+1)) % MOD;}LL C(int n, int m) { return ((1LL * fac[n] * inv[m]) % MOD * inv[n-m]) % MOD;}int main() { int n, m, up = 0; init(); scanf("%d %d", &n, &m); for (int i = 2; i*i <= m; i++) { if(m % i == 0) { int tmp = 0; while(m % i == 0) m /= i, tmp++; cnt[++up] = tmp; } } if(m > 1) cnt[++up] = 1; LL ans = 1; for (int i = 1; i <= up; i++) ans = (ans * C(cnt[i]+n-1, n-1)) % MOD; printf("%lld\n", ans); return 0;}

 

转载于:https://www.cnblogs.com/widsom/p/9696297.html

你可能感兴趣的文章
(原)InsightFace及其mxnet代码
查看>>
OpenCV学习:实现简单的图像叠加
查看>>
Intent跳转到系统应用中的拨号界面、联系人界面、短信界面及其他
查看>>
java.io包的总体框架图(转)
查看>>
VKDevTool App黑盒调试工具
查看>>
那个你身边悄悄离职的人去哪儿了?IT人才流动大盘点
查看>>
精读《手写 SQL 编译器 - 智能提示》
查看>>
Java多线程干货系列—(四)volatile关键字| 掘金技术征文
查看>>
我们来翻翻元素样式的族谱-getComputedStyle
查看>>
Hessian HTTP POST访问时,Nginx返回411问题
查看>>
Redux进阶系列2: 如何合理地设计State
查看>>
[译] 部署!=发布(第二部分)
查看>>
数据结构和算法面试题系列—C指针、数组和结构体
查看>>
Android解析ActivityManagerService(一)AMS启动流程和AMS家族
查看>>
大前端开发者需要了解的基础编译原理和语言知识
查看>>
Exif图片方向的一些发现
查看>>
iOS关联对象
查看>>
Javascript如何实现GPU加速?
查看>>
次世代的会话管理项目 Spring Session
查看>>
SQL SERVER 2008安全配置
查看>>