首页 > Coprime Subsequences
开通博客写题解
头像 issue是云哥的小迷×呀
发表于 2021-02-25 17:26:46
考虑先求出最大公约数大于的子序列个数 显然,我们可以枚举这个最大公约数 我们预处理一个表示有个数字含有约数 然后我们去枚举子序列的最大公约数来计算答案 我们定义表示最大公约数是倍数的方案数 怎么求最大公约数是的方案数呢?? 我们定义表示最大公约数是的方案数 那么 预处理数组的复杂度,直接质因子分解 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 shyyhs
发表于 2021-02-24 23:46:10
题目: 问你有多少子序列gcd为1. 思路: gcd为的数,是不是等于都包含因子的个数-包含因子的个数-包含因子的个数-包含因子5的个数+包含因子的个数...这样容斥一下.其实就是一个莫比乌斯函数.包含因子的个数的子序列,假设因子是个,那么方案数是不是.选/不选-全不选. 代码: #include 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 sunrise__sunrise
发表于 2021-02-27 21:28:25
中文题意 给你个数，问你从中挑选非空的子序列并且保证子序列的子序列数量有多少个。 。 Solution 正向不太好做，那么就反向思考，我们可以选择的总的子序列个数是个。减去选择一个素数这些子序列个数，再加上选择两个不同素数乘积这些的子序列数量，再减去选择三个素数的，依次容斥就是答案了。注意我们还需要 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Eihuvita.
发表于 2021-03-01 21:12:10
题意 给你n个数让你从中挑选一个非空子序列，使得子序列 问有多少个这样的非空子集 解析 我太菜了理解了好久这个容斥 首先来说就是正着求我们不好求 那么我们就去反过来求 把所有的 减去不等于1的 那么来分析一下有哪些不等于1的情况 简单来说就是有两个以上的数字他们有着一个相同的因子，那个因子就可以是 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 hnust_yangyanjun
发表于 2021-03-05 11:44:13
题意：给你一个长度为n的序列，让你求序列的最大公约数为1的子序列数目为多少？ 思路：莫比乌斯反演首先统计一下该序列有什么数，个数为多少。然后求莫比乌斯函数。统计有i为因子的数有x。根据x求都有该因子的序列有 ( )个根据莫比乌斯函数判断该序列数是加上还是减去.最后得出结果. 代码： #include 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 熠丶
发表于 2021-02-28 17:32:33
题意 给你一个序列，问你有多少个子序列它们的最大公约数为1 思路 先求出这些数中有多少个数含因子i 公约数为i的序列数为 代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp( 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 zqy1018_
发表于 2021-02-25 10:57:04
题意 给定一正整数序列 ，问有多少个非空子序列使得其中所有数的 为 1。 题解 容斥，设 为 为 的倍数，的非空子序列个数。那么如果 中有 个数是 的倍数那么 。 设 为 恰为 的非空子序列个数。那么 。 时间复杂度 ，其中 。 #include <bits/stdc++. 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”