首页 > 代码库 > 两句话题意 感觉这一题的套路很强
两句话题意 感觉这一题的套路很强
http://acm.uestc.edu.cn/#/problem/show/1171
颠覆了我求gcd的思路,以前的都是mobius求gcd = 1的,现在的这个能求所有的。
设ans[i]表示gcd = i的集合数。
那么需要求ans[k],我们需要知道所有k、2*k、3*k......的元素的个数总和。
那么所有可能的集合数是2^cnt - 1
但是比如要算2,先求出2、4、6、8、10、......的总和,这样的算出来的集合有可能产生gcd = k的倍数的不合法情况。
需要减去,假设是逆序求,则ans[k * i]的就早已经算出来了,减去即可。复杂度nlnn
注意模数不是1e9+7
#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> LL quick_pow(LL a, LL b, LL MOD) { LL ans = 1; LL base = a; while (b) { if (b & 1) { ans = ans * base % MOD; } b >>= 1; base = base * base % MOD; } return ans; } const int maxn = 2e6 + 20; int ans[maxn], num[maxn]; const int MOD = 10000007; void work() { int n, k; scanf("%d%d", &n, &k); int mx = -inf; for (int i = 1; i <= n; ++i) { int x; scanf("%d", &x); num[x]++; mx = max(mx, x); } LL res = 0; if (num[0]) { ans[0] = (quick_pow(2, num[0], MOD) - 1 + MOD) % MOD; res = ans[0]; } for (int i = mx; i >= 1; --i) { int has = num[0]; for (int j = i; j <= mx; j += i) has += num[j]; ans[i] = (quick_pow(2, has, MOD) - 1 + MOD) % MOD; for (int j = 2 * i; j <= mx; j += i) { ans[i] = (ans[i] - ans[j] + MOD) % MOD; } ans[i] = (ans[i] - ans[0] + MOD) % MOD; res = (res + quick_pow(i, k, MOD) * ans[i] % MOD) % MOD; } cout << res << endl; for (int i = 0; i <= mx; ++i) ans[i] = num[i] = 0; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif int t; scanf("%d", &t); while (t--) { work(); // printf("\n"); } return 0; }
两句话题意 感觉这一题的套路很强
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。