首页 > 代码库 > URAL 1091. Tmutarakan Exams 容斥
URAL 1091. Tmutarakan Exams 容斥
从1到s选出k个数 他们的最大公约数大于1 求方案数
容斥 S(1)-S(2)+S(3) S(x)为选出k个数的公因子个数为x的数量
#include <cstdio> #include <cmath> #include <cstring> using namespace std; typedef long long LL; const int maxn = 55; int prime[maxn], vis[maxn]; int n, m; int get_primes(int n) { int m = sqrt(n+0.5), c = 0; for(int i = 2; i <= n; i++) if(!vis[i]) { prime[c++] = i; for(int j = i*2; j <= n; j += i) { vis[j] = 1; } } return c; } LL cm(int n, int m) { LL ans = 1; for(int i = 1; i <= m; i++) { ans *= (LL)n--; ans /= (LL)i; } return ans; } void dfs(int i, int x, int k, int m, LL& ans, int c) { if(i == c) { if(!k) return; if(k&1) ans += cm(m/x, n); else ans -= cm(m/x, n); return; } dfs(i+1, x*prime[i], k+1, m, ans, c); dfs(i+1, x, k, m, ans, c); } LL cal(int c) { LL ans = 0; dfs(0, 1, 0, m, ans, c); if(ans > 10000) ans = 10000; return ans; } int main() { int c = get_primes(50); //printf("%d\n", c); while(scanf("%d %d", &n, &m) != EOF) { printf("%lld\n", cal(c)); } return 0; }
URAL 1091. Tmutarakan Exams 容斥
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。