https://codeforces.com/contest/1541/problem/B
시간 1초, 메모리 256MB
input :
- t (1 ≤ t ≤ 104)
- n (1 ≤ n ≤ 105)
- a1, a2, ..., an(1 <= ai <= 2 * n)
output :
- For each test case, output the number of pairs of indices (i,j) such that i<j and ai⋅aj=i+j.
각 테스크 케이스에서 ai * aj = i + j와 i < j를 만족하는 개수를 출력하도록 하시오.
조건 :
- You are given an array a1, a2, ..., an consisting of n distinct integers
모든 원소들은 다 다른 수로 이루어져 있다.
이 때 가능한 경우를 찾으라는 것인데
당연히 모든 것들을 확인하게 한다면 시간초과가 발생한다.
시간을 줄이려면 필요한 것이 범위를 제한해야 하는데 i + j를 이용해야 한다.
인덱스의 경우 언제나 범위가 존재하기 때문에 얘네를 이용해 원소의 곱을 제한 할 수 있다.
어차피 모든 원소의 크기는 다르니까 원소의 값과, 인덱스를 저장하도록 하고
원소의 값에 따라 정렬을 한다.
그리고 이 값을 곱하면서 2 * n보다 커지는 경우 반복을 그만 하고 다음 원소로 넘어간다.
뒤로 갈수록 커져서? 시간이 제한 된다.
그리고 또 다른 방법으로는 물론 동일하게 범위를 제한하는데 제한하고 난 후에
내가 찾으려는 수를 x(원소 두 개의 곱이라고 예상)를 찾는데.
이 x가 두 수의 곱으로 이루어졌다는 것은 약수들로 이루어졌다고 볼 수도 있다.
약수로 따지게 된다면 만약 x가 12일 때, 1 2 3 4 6 12이렇게 볼 수 있는데
이 부분의 반으로 우리는 해당하는 원소가 존재하는 지 확인 할 수 있다.
1 2 3만을 통해서 나머지를 볼 수 있는 것이다. 그래서 sqrt(12)의 값까지 체크를 하면서 찾을 수 도 있다.
import sys
for _ in range(int(sys.stdin.readline())):
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
temp, ans = [], 0
for i in range(n):
temp.append([data[i], i + 1])
temp.sort()
for i in range(n):
for j in range(i + 1, n):
if temp[i][0] * temp[j][0] > 2 * n:
break
if temp[i][0] * temp[j][0] == temp[i][1] + temp[j][1]:
ans += 1
print(ans)
