Submission #6783943


Source Code Expand

def div(n):
  ret=[]
  for i in range(1,int(n**0.5)+1):
    if n%i==0:
      ret.append(i)
      if i!=n//i:
        ret.append(n//i)
  return ret

def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)

n,k=map(int,input().split())
arr=list(map(int,input().split()))
gcds={}
for val in arr:
  tmp=gcd(val,k)
  if tmp not in gcds:
    gcds[tmp]=1
  else:
    gcds[tmp]+=1
ans=0
divs=div(k)
for val1 in divs:
  for val2 in divs:
    if (val1*val2)%k!=0:
      continue
    if val1==val2:
      if val1 in gcds:
        ans+=gcds[val1]*(gcds[val2]-1)
    else:
      if val1 in gcds and val2 in gcds:
        ans+=gcds[val1]*gcds[val2]        
print(ans//2)

Submission Info

Submission Time
Task C - ロト2
User tanon710
Language Python (3.4.3)
Score 400
Code Size 704 Byte
Status AC
Exec Time 653 ms
Memory 27308 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 25
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 10_random_01.txt, 10_random_02.txt, 10_random_03.txt, 10_random_04.txt, 10_random_05.txt, 20_max_01.txt, 20_max_02.txt, 20_max_03.txt, 20_max_04.txt, 20_max_05.txt, 30_overflow_01.txt, 30_overflow_02.txt, 40_dmax_01.txt, 40_dmax_02.txt, 40_dmax_03.txt, 50_prime_01.txt, 50_prime_02.txt, 50_prime_03.txt, 60_prime_pow_01.txt, 60_prime_pow_02.txt, 60_prime_pow_03.txt, 70_one_01.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 17 ms 3064 KB
00_example_02.txt AC 17 ms 3064 KB
00_example_03.txt AC 17 ms 3064 KB
10_random_01.txt AC 17 ms 3064 KB
10_random_02.txt AC 18 ms 3064 KB
10_random_03.txt AC 17 ms 3064 KB
10_random_04.txt AC 18 ms 3064 KB
10_random_05.txt AC 17 ms 3064 KB
20_max_01.txt AC 236 ms 25320 KB
20_max_02.txt AC 227 ms 23860 KB
20_max_03.txt AC 336 ms 23948 KB
20_max_04.txt AC 219 ms 24632 KB
20_max_05.txt AC 403 ms 25708 KB
30_overflow_01.txt AC 232 ms 21540 KB
30_overflow_02.txt AC 245 ms 22784 KB
40_dmax_01.txt AC 618 ms 24316 KB
40_dmax_02.txt AC 653 ms 26440 KB
40_dmax_03.txt AC 625 ms 26444 KB
50_prime_01.txt AC 245 ms 23904 KB
50_prime_02.txt AC 290 ms 26016 KB
50_prime_03.txt AC 340 ms 27308 KB
60_prime_pow_01.txt AC 332 ms 25100 KB
60_prime_pow_02.txt AC 333 ms 26060 KB
60_prime_pow_03.txt AC 334 ms 24760 KB
70_one_01.txt AC 162 ms 22292 KB