[CF 1043F] Make It One

时间：2021-10-05 01:31:34

Description

给定 \(n\) 个正整数 \(a_i\)，最少选出多少个 \(a_i\) 使得他们 \(gcd\) 为 \(1\)？\(n,a_i\le 3\times 10^5\)。

Solution

设 \(f[i][j]\) 表示取出 \(i\) 个数、\(gcd\) 为 \(j\) 的方案数，\(cnt[i]\) 表示有多少个数有 \(i\) 这个约数。有：

\[f[i][j] = \binom{cnt[j]}{i}-f[i][j*k](k\ge 2)
\]

Code


[CF 1043F] Make It One的更多相关文章

  1. ORA-00494: enqueue [CF] held for too long (more than 900 seconds) by 'inst 1, osid 5166'

    凌晨收到同事电话,反馈应用程序访问Oracle数据库时报错,当时现场现象确认: 1. 应用程序访问不了数据库,使用SQL Developer测试发现访问不了数据库.报ORA-12570 TNS:pac ...

  2. cf之路，1，Codeforces Round #345 (Div. 2)

     cf之路,1,Codeforces Round #345 (Div. 2) ps:昨天第一次参加cf比赛,比赛之前为了熟悉下cf比赛题目的难度.所以做了round#345连试试水的深浅.....   ...

  3. cf Round 613

    A.Peter and Snow Blower(计算几何) 给定一个点和一个多边形,求出这个多边形绕这个点旋转一圈后形成的面积.保证这个点不在多边形内. 画个图能明白 这个图形是一个圆环,那么就是这个 ...

  4. ARC下OC对象和CF对象之间的桥接(bridge)

    在开发iOS应用程序时我们有时会用到Core Foundation对象简称CF,例如Core Graphics.Core Text,并且我们可能需要将CF对象和OC对象进行互相转化,我们知道,ARC环 ...

  5. [Recommendation System] 推荐系统之协同过滤（CF）算法详解和实现

    1 集体智慧和协同过滤 1.1 什么是集体智慧(社会计算)? 集体智慧 (Collective Intelligence) 并不是 Web2.0 时代特有的,只是在 Web2.0 时代,大家在 Web ...

  6. CF memsql Start[c]UP 2.0 A

    CF memsql Start[c]UP 2.0 A A. Golden System time limit per test 1 second memory limit per test 256 m ...

  7. CF memsql Start[c]UP 2.0 B

    CF memsql Start[c]UP 2.0 B B. Distributed Join time limit per test 1 second memory limit per test 25 ...

  8. CF #376 (Div. 2) C. dfs

    1.CF #376 (Div. 2)    C. Socks       dfs 2.题意:给袜子上色,使n天左右脚袜子都同样颜色. 3.总结:一开始用链表存图,一直TLE test 6 (1)如果需 ...

  9. CF #375 (Div. 2) D. bfs

    1.CF #375 (Div. 2)  D. Lakes in Berland 2.总结:麻烦的bfs,但其实很水.. 3.题意:n*m的陆地与水泽,水泽在边界表示连通海洋.最后要剩k个湖,总要填掉多 ...

随机推荐

  1. Linux下xampp集成环境安装配置方法 、部署bugfree及部署禅道

    XAMPP(Apache+MySQL+PHP+PERL)是一个功能强大的建站集成软件包.XAMPP 是一个易于安装且包含 MySQL.PHP 和 Perl 的 Apache 发行版.XAMPP 的确非 ...

  2. 10款免费而优秀的图表JS插件

    http://www.open-open.com/lib/view/open1406378625726.html http://www.ichartjs.com http://echarts.baid ...

  3. 2013长沙赛区现场赛 J - Josephina and RPG

    J - Josephina and RPG Time Limit:2000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I6 ...

  4. 线段树——Ultra-QuickSort

    题目网址:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=109331#problem/A Description In this prob ...

  5. mediastream2使用指南(转载)

    http://blog.sina.com.cn/s/blog_59d649610100diui.html 定义 Filter: 媒体库中处理数据的组件.一个filter有0到数个输入流和0到数个输出流 ...

  6. oracle11g创建数据库最后一步确定时弹出无法创建目录

    总的说是Windows7的权限问题 Windows7 dos命令下输入dbca创建数据库,因为权限问题,数据库将无法完成.所以还是在开始程序中打开dbca创建数据库比较好. Windows7 dos以 ...

  7. clion 帮助文档 EN

    下载时间 2015年10月 下载地址:http://pan.baidu.com/s/1E4fgE 备用地址:链接:http://pan.baidu.com/s/1bn6u5Wj 密码:icn4

  8. 在eclipse.ini中指定jdk的方式

    在eclisep的安装目录,打开eclipse.ini文件,加上这么一行,如下红色所示,注意加在-Vmargs前面,这两种方式的区别是:第二种方式除了会有eclipse进程外还会启动个java进程. ...

  9. 教你怎么把iconfont转换成png透明图片

    1.进入iconfont图标库,登陆.http://www.iconfont.cn/ 2.选择想要的图标加入购物车. 3.直接选中下载图标为png格式.

  10. vue目录结构

    构建新的项目后生成目录结构如下图: 1.build目录下: 最终发布de代码存放的位置 2.config 配置目录,包括端口号等.我们初学可以使用默认的 3.node_modules npm加载的项目 ...

相关文章