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\) 这个约数。有:

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

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

Code

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄