当前位置:网站首页>求组合数 AcWing 888. 求组合数 IV
求组合数 AcWing 888. 求组合数 IV
2022-07-05 06:16:00 【T_Y_F666】
求组合数 AcWing 888. 求组合数 IV
原题链接
算法标签
组合数学 组合计数 高精度
思路
代码
#include<bits/stdc++.h>
#define int long long
#define abs fabs
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
const int N = 5015;
int pr[N], st[N], s[N], cnt;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void put(int x) {
if(x<0) putchar('-'),x=-x;
if(x>=10) put(x/10);
putchar(x%10^48);
}
void pri(int n){
rep(i, 2, n+1){
if(!st[i]){
pr[cnt++]=i;
}
for(int j=0; pr[j]<=n/i; ++j){
st[pr[j]*i]=true;
if(!(i%pr[j])){
break;
}
}
}
}
int get(int n, int p){
int res=0;
while(n){
res+=n/p;
n/=p;
}
return res;
}
vector<int> mul(vector<int> a, int b){
vector<int> c;
int t=0;
rep(i, 0, a.size()){
t+=a[i]*b;
c.push_back(t%10);
t/=10;
}
while(t){
c.push_back(t%10);
t/=10;
}
return c;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int a=read(), b=read();
pri(a);
rep(i, 0, cnt){
int p=pr[i];
s[i]=get(a, p)-get(a-b, p)-get(b, p);
}
vector<int> res;
res.push_back(1);
rep(i, 0, cnt){
rep(j, 0, s[i]){
res=mul(res, pr[i]);
}
}
Rep(i, res.size()-1, 0){
printf("%lld", res[i]);
}
}
原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈
边栏推荐
- 1.14 - assembly line
- [rust notes] 17 concurrent (Part 1)
- 1040 Longest Symmetric String
- Leetcode-6108: decrypt messages
- 【Rust 笔记】14-集合(上)
- Erreur de connexion Navicat à la base de données Oracle Ora - 28547 ou Ora - 03135
- Data visualization chart summary (I)
- LeetCode 0107. Sequence traversal of binary tree II - another method
- [rust notes] 14 set (Part 2)
- Error ora-28547 or ora-03135 when Navicat connects to Oracle Database
猜你喜欢
LeetCode-61
Appium基础 — 使用Appium的第一个Demo
Liunx starts redis
Open source storage is so popular, why do we insist on self-development?
Navicat連接Oracle數據庫報錯ORA-28547或ORA-03135
Leetcode-6108: decrypt messages
中国剩余定理 AcWing 204. 表达整数的奇怪方式
SQL三种连接:内连接、外连接、交叉连接
阿里新成员「瓴羊」正式亮相,由阿里副总裁朋新宇带队,集结多个核心部门技术团队
传统数据库逐渐“难适应”,云原生数据库脱颖而出
随机推荐
MySQL advanced part 2: the use of indexes
Sqlmap tutorial (1)
Daily question 1189 Maximum number of "balloons"
1039 Course List for Student
JS quickly converts JSON data into URL parameters
Groupbykey() and reducebykey() and combinebykey() in spark
Error ora-28547 or ora-03135 when Navicat connects to Oracle Database
Regulations for network security events of vocational group in 2022 Guizhou Vocational College skill competition
1041 Be Unique
[rust notes] 15 string and text (Part 1)
Matrixdb V4.5.0 was launched with a new mars2 storage engine!
Leetcode-6110: number of incremental paths in the grid graph
Leetcode-22: bracket generation
快速使用Amazon MemoryDB并构建你专属的Redis内存数据库
中国剩余定理 AcWing 204. 表达整数的奇怪方式
SQLMAP使用教程(一)
[rust notes] 16 input and output (Part 1)
MySQL advanced part 2: SQL optimization
How to set the drop-down arrow in the spinner- How to set dropdown arrow in spinner?
SPI details