Déjà vu

한 부분수열의 $f(b)$에는 모든 원소에서 지수가 같은 소수 거듭제곱만 남는다. 예를 들어 $12=2^2\cdot3$, $20=2^2\cdot5$에서는 $2^2$만 남겨 $f((12,20))=4$를 얻는다.

$d\mid x$이고 $\gcd(d,x/d)=1$이면 $d\parallel x$라고 쓰자. 즉, $$를 소인수분해한 뒤 각 소수 거듭제곱을 통째로 선택하거나 버려서 얻는 약수이다. 라 하고, 각 에 대해 를 구한다. 각 값의 빈도를 세고, 소수 거듭제곱들의 부분집합 곱을 열거하면 된다.

$E_d$를 $f(b)=d$인 부분수열의 개수라고 하자. 먼저 $E_d=2^{c_d}-1$로 초기화한다. 이후 순서로, 의 모든 약수 , 에 대해 에서 를 뺀다. 정답은

$$\sum_{d=1}^{A}dE_d$$

이며, 모든 계산은 $998\,244\,353$을 법으로 한다.

최소 소인수와 $2$의 거듭제곱을 미리 계산하면 한 케이스의 시간 복잡도는 $O(N+A\log A)$, 공간 복잡도는 $O(N+A)$이다.

증명

소수 $p$의 지수가 $e_i$인 원소에 $p$를 고르는 연산을 $r$번 적용하면 그 지수는 $\max (e_i$이 된다. 지수가 모두 같으면 그대로 남기는 것이 최선이다. 서로 다르면 같은 값이 되기 위해 모두 이 되어야 한다. 따라서 에는 모든 원소에서 지수가 같은 양의 소수 거듭제곱만 남는다.