牛客数字染色莫比乌斯容斥
题目
给出一个正整数序列,求有多少子序列的gcd不为1。
求解
假设子序列gcd为x,那么只需求出x的倍数的数量m,gcd为x的子序列数量即为$2^m-1$。
这样可以求出 gcd分别为2的倍数、3的倍数、4的倍数… 的方案数,剩下的就是容斥了,比如6,计算2的倍数、3的倍数的时候重复算了,那么要减去。
代码:
1 |
|
那时候年轻,不知道命运赠送的礼物,早已在暗中标好价格。
缺失模块。
1、请确保node版本大于6.2
2、在博客根目录(注意不是yilia根目录)执行以下命令:
npm i hexo-generator-json-content
--save
3、在根目录_config.yml里添加配置:
jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: true tags: true