#745456 (PyPy3) No.1262 グラフを作ろう！

提出ソース

結果

問題	No.1262 グラフを作ろう！
ユーザー	chineristAC
提出日時	2022-03-12 01:59:29
言語	PyPy3 (7.3.15)
結果	AC
実行時間	701 ms / 3,000 ms
コード長	910 bytes
コンパイル時間	1,196 ms
コンパイル使用メモリ	86,888 KB
実行使用メモリ	254,420 KB
最終ジャッジ日時	2023-10-14 11:31:58
合計ジャッジ時間	61,917 ms
ジャッジサーバーID （参考情報）	judge13 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	645 ms 247,476 KB
testcase_01	AC	474 ms 182,112 KB
testcase_02	AC	539 ms 246,484 KB
testcase_03	AC	523 ms 252,264 KB
testcase_04	AC	312 ms 99,316 KB
testcase_05	AC	404 ms 165,976 KB
testcase_06	AC	316 ms 95,852 KB
testcase_07	AC	337 ms 102,876 KB
testcase_08	AC	423 ms 160,084 KB
testcase_09	AC	570 ms 184,268 KB
testcase_10	AC	399 ms 165,432 KB
testcase_11	AC	484 ms 169,284 KB
testcase_12	AC	542 ms 228,580 KB
testcase_13	AC	590 ms 252,520 KB
testcase_14	AC	416 ms 150,932 KB
testcase_15	AC	511 ms 165,064 KB
testcase_16	AC	543 ms 171,356 KB
testcase_17	AC	440 ms 170,460 KB
testcase_18	AC	666 ms 246,672 KB
testcase_19	AC	417 ms 101,544 KB
testcase_20	AC	442 ms 142,620 KB
testcase_21	AC	654 ms 224,820 KB
testcase_22	AC	307 ms 95,948 KB
testcase_23	AC	546 ms 170,908 KB
testcase_24	AC	440 ms 171,380 KB
testcase_25	AC	304 ms 97,340 KB
testcase_26	AC	325 ms 116,460 KB
testcase_27	AC	434 ms 150,336 KB
testcase_28	AC	366 ms 148,844 KB
testcase_29	AC	480 ms 121,744 KB
testcase_30	AC	490 ms 143,148 KB
testcase_31	AC	701 ms 224,516 KB
testcase_32	AC	506 ms 159,792 KB
testcase_33	AC	368 ms 143,324 KB
testcase_34	AC	456 ms 158,468 KB
testcase_35	AC	547 ms 228,548 KB
testcase_36	AC	530 ms 156,588 KB
testcase_37	AC	544 ms 246,720 KB
testcase_38	AC	432 ms 166,928 KB
testcase_39	AC	417 ms 166,148 KB
testcase_40	AC	408 ms 166,416 KB
testcase_41	AC	387 ms 132,144 KB
testcase_42	AC	593 ms 208,984 KB
testcase_43	AC	384 ms 150,876 KB
testcase_44	AC	381 ms 166,844 KB
testcase_45	AC	464 ms 188,596 KB
testcase_46	AC	359 ms 116,496 KB
testcase_47	AC	564 ms 203,984 KB
testcase_48	AC	468 ms 187,632 KB
testcase_49	AC	482 ms 251,984 KB
testcase_50	AC	589 ms 206,412 KB
testcase_51	AC	443 ms 207,732 KB
testcase_52	AC	340 ms 126,572 KB
testcase_53	AC	329 ms 112,840 KB
testcase_54	AC	463 ms 215,964 KB
testcase_55	AC	431 ms 188,320 KB
testcase_56	AC	347 ms 132,392 KB
testcase_57	AC	490 ms 231,196 KB
testcase_58	AC	468 ms 247,328 KB
testcase_59	AC	358 ms 131,428 KB
testcase_60	AC	482 ms 254,420 KB
testcase_61	AC	372 ms 157,776 KB
testcase_62	AC	464 ms 249,840 KB
testcase_63	AC	472 ms 232,660 KB
testcase_64	AC	405 ms 171,164 KB
testcase_65	AC	315 ms 109,300 KB
testcase_66	AC	361 ms 158,028 KB
testcase_67	AC	344 ms 136,916 KB
testcase_68	AC	325 ms 109,152 KB
testcase_69	AC	372 ms 142,496 KB
testcase_70	AC	447 ms 182,856 KB
testcase_71	AC	428 ms 172,060 KB
testcase_72	AC	456 ms 208,356 KB
testcase_73	AC	496 ms 232,496 KB
testcase_74	AC	490 ms 251,588 KB
testcase_75	AC	465 ms 206,564 KB
testcase_76	AC	429 ms 170,512 KB
testcase_77	AC	457 ms 230,476 KB
testcase_78	AC	432 ms 189,680 KB
testcase_79	AC	477 ms 249,844 KB
testcase_80	AC	410 ms 170,292 KB
testcase_81	AC	446 ms 230,220 KB
testcase_82	AC	477 ms 232,604 KB
testcase_83	AC	428 ms 170,252 KB
testcase_84	AC	433 ms 171,528 KB
testcase_85	AC	477 ms 215,856 KB
testcase_86	AC	480 ms 225,724 KB
testcase_87	AC	508 ms 251,472 KB
testcase_88	AC	498 ms 230,208 KB
testcase_89	AC	437 ms 159,732 KB
testcase_90	AC	509 ms 232,408 KB
testcase_91	AC	514 ms 232,444 KB
testcase_92	AC	496 ms 232,436 KB
testcase_93	AC	487 ms 240,796 KB
testcase_94	AC	483 ms 232,880 KB
testcase_95	AC	481 ms 232,432 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

def ind(b,n):
    res=0
    while n%b==0:
        res+=1
        n//=b
    return res

def eratosthenes(n):
    spf = [0 for i in range(n+1)]
    for i in range(2,n+1):
        if not spf[i]:
            for j in range(1,n//i+1):
                spf[i*j] = i
    return spf

#spf = eratosthenes(10**6)

def euler_phi(n):
    phi = [1 for i in range(n+1)]
    for i in range(2,n+1):
        if phi[i] == 1:
            for j in range(1,n//i+1):
                t = 1
                tmp = j
                while tmp%i==0:
                    t *= i
                    tmp //= i
                phi[i*j] *= t*(i-1)
    return phi

phi = euler_phi(10**6)

N,M = map(int,input().split())
A = list(map(int,input().split()))
data = [0 for i in range(10**6+1)]
for a in A:
    data[a] += 1

res = - sum(A)
for i in range(1,10**6+1):
    for j in range(1,10**6//i+1):
        res += (i)*phi[j]*data[i*j]

print(res)

yukicoder

結果

テストケース

ソースコード