[LeetCode]周賽335 Problem 3-Solution

2023-03-05 12:16 作者:故寓諸無竟 0人讀過 | 我要投稿

題目簡述

????????給定一個長度為 $n$ 的序列 $%5C%7Ba_i%5C%7D$ ，將其分為前后非空兩段，使得前后兩段的乘積互質(zhì)，并輸出分割點。如果分割點不存在，輸出 $-1$ 。

????????原題目鏈接：https://leetcode.cn/contest/weekly-contest-335/problems/split-the-array-to-make-coprime-products/

思路1

????????如果直接從左到右枚舉分割點，并維護左右乘積，看似復(fù)雜度合理，但由于數(shù)值過大，必須使用高精度gcd，這樣實際的復(fù)雜度（包括時間和編程難度）都很大。

????????一般對于gcd，可以從因子來考慮。我們將 $%5C%7Ba_i%5C%7D$ 中的所有數(shù)分解質(zhì)因數(shù)，然后枚舉分割點并維護左右乘積的分解結(jié)果就可以了。只要使用合理的維護技巧（見附錄），復(fù)雜度可以做到 $O(n%5Csqrt%7Bn%7D%20%2B%20v)$ 。其中 $O(v)$ 是篩素數(shù)的復(fù)雜度， $v%5Cle%2010%5E6$ 。

????????由于質(zhì)數(shù)數(shù)目的特性（ $%5Clim%20%5Climits_%7Bx%5Cto%20%5Cinfty%7D%20%5Cpi(x)%20%5Csim%20%5Cfrac%7Bx%7D%7B%5Cln%20x%7D$ ），因此 $v$ 以內(nèi)的素數(shù)數(shù)目也是萬級別，因此也不妨嘗試直接暴力維護乘積，復(fù)雜度為 $O(n%5Csqrt%7Bn%7D%20%2B%20nv)$ 。如果不放心，可以使用bitset（比如我）優(yōu)化到 $O(n%5Csqrt%7Bn%7D%20%2B%20%5Cfrac%7Bnv%7D%7Bw%7D)$ 。

思路2（未驗證）

????????在得到 $%5C%7Ba_i%5C%7D$ 中的所有數(shù)的質(zhì)因數(shù)分解后，從右到左枚舉每一個數(shù) $a_i$ ，與此同時維護當前每一個質(zhì)因子在數(shù)組中出現(xiàn)的最小下標。這樣我們可以得到對于每一個數(shù)而言，其后首個與它不互質(zhì)的數(shù)的位置 $p_i$ 。這樣，在 $i%5Csim%20(p_%7Bi%7D-1)$ 之間不可能存在分割點。我們標記這整個區(qū)間內(nèi)的位置為impossible。最后，枚舉分割點，找到最小的非impossible的分割點即可。

????????注意到每次標記一個連續(xù)的區(qū)間，因此使用差分進行標記，復(fù)雜度為 $O(n%5Csqrt%7Bn%7D%20%2B%20v)$ 。

????????備注：當然，其實也沒必要標記，可以直接根據(jù) $p_i$ 一直往后“跳”就可以了。

附錄

????????關(guān)于思路1中的維護策略。很簡單，只需要考慮每一個數(shù)所涉及的 $O(%5Csqrt%7Bn%7D)$ 個質(zhì)因子即可。用一個cnt變量記錄當前左右公共質(zhì)因子數(shù)目，在 $O(%5Csqrt%7Bn%7D)$ 更新中動態(tài)調(diào)整cnt。