当前位置:网站首页>Find the combination number acwing 888 Find the combination number IV
Find the combination number acwing 888 Find the combination number IV
2022-07-05 06:24:00 【T_ Y_ F666】
Find the combination number AcWing 888. Find the combination number IV
Original link
AcWing 888. Find the combination number IV
Algorithm tags
Combinatorial mathematics Combination count High precision
Ideas
Code
#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]);
}
}
Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support
边栏推荐
- Leetcode dynamic programming
- 11-gorm-v2-02-create data
- Error ora-28547 or ora-03135 when Navicat connects to Oracle Database
- Records of some tools 2022
- How to generate an image from text on fly at runtime
- Doing SQL performance optimization is really eye-catching
- RecyclerView的应用
- P3265 [jloi2015] equipment purchase
- Leetcode recursion
- 区间问题 AcWing 906. 区间分组
猜你喜欢
1.13 - RISC/CISC
1.手动创建Oracle数据库
[moviepy] unable to find a solution for exe
2021apmcm post game Summary - edge detection
Sqlmap tutorial (1)
[2021]IBRNet: Learning Multi-View Image-Based Rendering Qianqian
NotImplementedError: Cannot convert a symbolic Tensor (yolo_boxes_0/meshgrid/Size_1:0) to a numpy ar
LeetCode-61
Appium foundation - use the first demo of appium
Install opencv -- CONDA to establish a virtual environment and add the kernel of this environment in jupyter
随机推荐
Is it impossible for lamda to wake up?
Regulations for network security events of vocational group in 2022 Guizhou Vocational College skill competition
4. Oracle redo log file management
Navicat连接Oracle数据库报错ORA-28547或ORA-03135
Series of how MySQL works (VIII) 14 figures explain the atomicity of MySQL transactions and the principle of undo logging
求组合数 AcWing 889. 满足条件的01序列
AE tutorial - path growth animation
Applicable to Net free barcode API [off] - free barcode API for NET [closed]
1.13 - RISC/CISC
高斯消元 AcWing 884. 高斯消元解异或線性方程組
SQL三种连接:内连接、外连接、交叉连接
博弈论 AcWing 892. 台阶-Nim游戏
WordPress switches the page, and the domain name changes back to the IP address
4. Object mapping Mapster
How to make water ripple effect? This wave of water ripple effect pulls full of retro feeling
开源存储这么香,为何我们还要坚持自研?
[rust notes] 16 input and output (Part 2)
Redis publish subscribe command line implementation
【LeetCode】Easy | 20. Valid parentheses
快速使用Amazon MemoryDB并构建你专属的Redis内存数据库