首页 > 代码库 > UESTC - 1544 当咸鱼也要按照基本法 组合数学 容斥原理
UESTC - 1544 当咸鱼也要按照基本法 组合数学 容斥原理
http://acm.uestc.edu.cn/#/problem/show/1544
考虑一下2、2、2这样的情况。答案应该是n / 2
如果只选一个的情况下，对答案的贡献是正的，但是这里有三个，也就是我们统计了3 * n / 2，统计多了。
那么对于任选两个数的情况，有三种，(2, 2) * 3，分别都是不同位置的2，
/**************************************/
我做的时候是发现，先讨论只有
2、2的情况，也就是只有两个数的时候，ans = 0，这个时候，先模拟上面的，只选一个，答案是2 * n / 2
那么枚举两个数的情况，应该就是要ans -= 2 * n / (lcm(2, 2))
要减2倍，不然答案不是0.
/**************************************/
那么上面也是，有三种(2, 2)的情况，ans -= 3 * 2 * n / (lcm(2, 2))
那么现在是-3 * n / (lcm(2, 2))
然后还有一种的就是枚举三个的情况，要使答案是n / 2，那么应该加上4 * n / (lcm(2, 2))
然后得到的规律是1 << (sel - 1)，sel是选的数字个数。
完全是瞎比比的，数学不好。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> int n, has; const int maxn = 15 + 20; int arr[maxn]; LL ans; LL LCM(LL a, LL b) { return a / __gcd(a, b) * b; } void dfs(int cur, int sel, LL theLcm) { if (theLcm > n) return; if (cur == has + 1) { if (!sel) return; if (sel & 1) { ans += (1 << (sel - 1)) * (n / theLcm); } else { ans -= (1 << (sel - 1)) * (n / theLcm); } return; } dfs(cur + 1, sel, theLcm); dfs(cur + 1, sel + 1, LCM(theLcm, arr[cur])); } void work() { ans = 0; scanf("%d%d", &n, &has); for (int i = 1; i <= has; ++i) { scanf("%d", &arr[i]); } dfs(1, 0, 1); cout << ans << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif int t; scanf("%d", &t); while (t--) work(); return 0; }
还有就是数据中没有15个大质数这样的情况，数据比较弱。
UESTC - 1544 当咸鱼也要按照基本法 组合数学 容斥原理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。