https://projecteuler.net/problem=619


요약하면 집합 S = {a, a + 1, a + 2, ..., b}가 주어졌을때 S의 부분집합의 곱이 제곱수가 되는 경우의 수를 구하는건데요


일단  각 a <= n <= b 를 소인수 분해 했을때 각 소인수의 지수의 홀짝성만 중요하니까 각 n을 GF(2)상의 벡터로 나타낼수 있잖아요?


m = b - a + 1라고 했을때 구하고자 하는 답은 결국 a1 * v1 + a2 * v2 + ... + am * vm = 0을 만족하는 해의 개수인데, finite field에서는 답이 2^(m - 최대 선형독립 벡터 개수가) 맞죠?


그럼 결국 A = [v1, v2, v3, ..., vm] 의 랭크를 구해야 하는데 A가 엄청 크잖아요 (약  (<= b 소수 개수) x (b - a + 1))?


A가 sparse하니까 이걸 이용해서 효율적이게 구할수 있을것 같긴 한데, 파이썬에 이런거 구해주는 패키지 없나요? 일반 numpy.linalg.rank 함수는 sparse 행렬도 못구하는것 같고, 또 numpy/scipy 가 finite field 관련된 행렬 연산은 없는것 같던데..


직접 구현해야 할까요? 아님 제 접근법이 틀리거나 다른 더 좋은 방법이 있는건가요?