Subscribed unsubscribe Subscribe Subscribe

0w1

Sieve

CFR 803 F. Coprime Subsequences ( Inclusion Exclusion, Math, Sieve )

Problem - F - Codeforces題意: 給 N 個元素的數列 A。問有幾種不同的非空子序列,其最大公因數不為 1。輸出方案數對 1e9 + 7 取模。制約: The first line contains one integer number n (1 ≤ n ≤ 100000). The second line contains n integer numbers a…

CFR 757 B. Bash's Big Day ( Sieve )

Problem - B - Codeforces題意: 求最大團大小,滿足團裡所有 S[ i ] 的最大公因數不為 1。資料規模: 1 ≤ N ≤ 1e5 1 ≤ S[ i ] ≤ 1e5 TL: 2000 ms ML: 512 MB解法: 如果某個最大公因數 x 的倍數數量是最大可能的,那麼顯然對 x 的所有非 1 因數,倍數數量也…