DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選

Submission #6899253

Source codeソースコード

n,k=map(int,input().split())
a=list(map(int,input().split()))

def soinsuu(a):
    soinsuu_dict=dict()
    j=2
    while(a>1):
        for i in range(j,int(a**0.5)+1):
            if a%i==0:
                if i in soinsuu_dict.keys():
                    soinsuu_dict[i]+=1
                else:
                    soinsuu_dict[i]=1
                a,j=a//i,i
                break
        else:
            if a in soinsuu_dict.keys():
                soinsuu_dict[a]+=1
            else:
                soinsuu_dict[a]=1
            a=1
            break
    return soinsuu_dict

def yakusuu(a):
    yakusuu=set()
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            yakusuu.add(i)
            yakusuu.add(a//i)
    yakusuu=sorted(list(yakusuu),reverse=True)
    return yakusuu

soinsuu_dict=soinsuu(k)
y_k=yakusuu(k)
d={y:0 for y in y_k}
for i in a:
    temp=1
    for j in soinsuu_dict.keys():
        for _ in range(soinsuu_dict[j]):
            if i%j==0:
                i=i//j
                temp*=j
            else:
                break
    d[temp]+=1
    
ans=0
for y in y_k:
    for z in y_k:
        if y<z:
            if (y*z)%k==0:
                ans+=d[y]*d[z]
        elif y==z:
            if (y*z)%k==0:
                ans+=d[y]*(d[y]-1)//2
print(ans)

Submission

Task問題 C - ロト2
User nameユーザ名 tmg_dayo
Created time投稿日時
Language言語 Python3 (3.4.3)
Status状態 AC
Score得点 400
Source lengthソースコード長 1349 Byte
File nameファイル名
Exec time実行時間 1533 ms
Memory usageメモリ使用量 25772 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_example_01.txt,00_example_02.txt,00_example_03.txt
All 400 / 400 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_example_01.txt AC 18 ms 3064 KB
00_example_02.txt AC 18 ms 3064 KB
00_example_03.txt AC 18 ms 3064 KB
10_random_01.txt AC 18 ms 3064 KB
10_random_02.txt AC 20 ms 3064 KB
10_random_03.txt AC 18 ms 3064 KB
10_random_04.txt AC 19 ms 3064 KB
10_random_05.txt AC 18 ms 3064 KB
20_max_01.txt AC 500 ms 24040 KB
20_max_02.txt AC 247 ms 23864 KB
20_max_03.txt AC 455 ms 23952 KB
20_max_04.txt AC 348 ms 22504 KB
20_max_05.txt AC 414 ms 25200 KB
30_overflow_01.txt AC 494 ms 22680 KB
30_overflow_02.txt AC 487 ms 22784 KB
40_dmax_01.txt AC 1531 ms 25180 KB
40_dmax_02.txt AC 1533 ms 25340 KB
40_dmax_03.txt AC 1517 ms 24316 KB
50_prime_01.txt AC 250 ms 24744 KB
50_prime_02.txt AC 245 ms 22936 KB
50_prime_03.txt AC 505 ms 25772 KB
60_prime_pow_01.txt AC 1166 ms 25092 KB
60_prime_pow_02.txt AC 389 ms 23932 KB
60_prime_pow_03.txt AC 324 ms 24120 KB
70_one_01.txt AC 120 ms 22292 KB