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 |
|
|
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 |