E1. Square-free division (easy version) | Round #708 Div.2

https://codeforces.com/contest/1497/problem/E1
시간 1초, 메모리 256MB

input :

• t (1 ≤ t ≤ 1000)
• n k (1 ≤ n ≤ 2 * 105, k = 0)
• a1, a2, ..., an(1 <= ai <= 107)

output :

• For each test case print a single integer — the answer to the problem.
  각 테스트 케이스에서 문제에 대한 정답을 출력하시오.

조건 :

• You should divide it into a minimal number of continuous segments, such that in each segment there are no two numbers (on different positions), whose product is a perfect square.
  연속적인 부분배열로 배열을 구분 하는데 어떠한 두 수의 곱도 제곱수가 되지 않도록 한다.

---

모든 숫자에 대한 제곱수를 기록해둬야 한다.
1을 기준으로 봤을 때, 1 1 / 2 2 / 3 3/ ... / 10000000 10000000 까지의 수들은 이로 만들어진 두 수를 곱하면 제곱수가 된다. 맨 처음 1을 기준으로 잡았을 때 이 1도 다른 수에 1개 들어 있으니까.

그렇게 2, 3, 4, 5, ...., 10000000 까지 기록을 해서 모든 원소들을 비교해야 한다.
그래서 부분배열을 이루는 원소들의 기준들을 봤을 때 다 달라야 한다.
다르지 않다면 새로운 배열을 만든다.

어차피 연속적인 부분배열이기 때문에 처음 원소부터 끝까지 확인하면 된다.

hard의 경우에는 원소들을 재배치시키기도 하기 때문에 hard는 잘 모르겠다...(노력해보겠다.)

import sys

limit = 10000001
temp = [0] * limit

for i in range(1, limit):
    if temp[i] != 0:
        continue

    temp[i] = i
    # finding all the square number
    j = 1
    while i * j * j <= limit:
        temp[i * j * j] = i
        j += 1

for _ in range(int(sys.stdin.readline())):
    n, k = map(int, sys.stdin.readline().split())
    data = list(map(int, sys.stdin.readline().split()))

    # if they have same number in temp list
    # then if you multiply this two you'll get square number
    # because they have same counts of number and trigger number(index i)
    # will be multiply twice so it will be square number

    now = set()
    cnt = 1
    for item in data:
        if temp[item] in now:
            now = set()
            cnt += 1

        now.add(temp[item])

    print(cnt)