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

提出ソース

結果

問題	No.1262 グラフを作ろう！
ユーザー	chineristAC
提出日時	2020-10-16 22:13:04
言語	PyPy3 (7.3.15)
結果	AC
実行時間	901 ms / 3,000 ms
コード長	841 bytes
コンパイル時間	1,238 ms
コンパイル使用メモリ	82,460 KB
実行使用メモリ	254,792 KB
最終ジャッジ日時	2023-09-28 03:29:12
合計ジャッジ時間	74,866 ms
ジャッジサーバーID （参考情報）	judge14 / judge11

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	883 ms 248,076 KB
testcase_01	AC	676 ms 189,556 KB
testcase_02	AC	764 ms 252,868 KB
testcase_03	AC	745 ms 213,640 KB
testcase_04	AC	561 ms 99,756 KB
testcase_05	AC	687 ms 165,936 KB
testcase_06	AC	560 ms 95,644 KB
testcase_07	AC	628 ms 109,112 KB
testcase_08	AC	763 ms 163,764 KB
testcase_09	AC	694 ms 191,504 KB
testcase_10	AC	662 ms 165,712 KB
testcase_11	AC	751 ms 173,176 KB
testcase_12	AC	798 ms 235,596 KB
testcase_13	AC	901 ms 213,092 KB
testcase_14	AC	820 ms 150,976 KB
testcase_15	AC	795 ms 168,848 KB
testcase_16	AC	828 ms 178,572 KB
testcase_17	AC	738 ms 177,792 KB
testcase_18	AC	835 ms 254,792 KB
testcase_19	AC	594 ms 106,992 KB
testcase_20	AC	693 ms 137,608 KB
testcase_21	AC	759 ms 231,092 KB
testcase_22	AC	532 ms 95,456 KB
testcase_23	AC	692 ms 174,560 KB
testcase_24	AC	746 ms 178,384 KB
testcase_25	AC	529 ms 104,328 KB
testcase_26	AC	579 ms 119,580 KB
testcase_27	AC	695 ms 150,404 KB
testcase_28	AC	662 ms 143,520 KB
testcase_29	AC	638 ms 120,436 KB
testcase_30	AC	682 ms 137,884 KB
testcase_31	AC	800 ms 230,316 KB
testcase_32	AC	719 ms 163,432 KB
testcase_33	AC	666 ms 137,600 KB
testcase_34	AC	740 ms 158,464 KB
testcase_35	AC	782 ms 235,808 KB
testcase_36	AC	682 ms 149,456 KB
testcase_37	AC	795 ms 213,948 KB
testcase_38	AC	776 ms 152,712 KB
testcase_39	AC	709 ms 174,092 KB
testcase_40	AC	682 ms 151,968 KB
testcase_41	AC	697 ms 128,160 KB
testcase_42	AC	843 ms 217,156 KB
testcase_43	AC	661 ms 151,168 KB
testcase_44	AC	715 ms 151,880 KB
testcase_45	AC	789 ms 195,512 KB
testcase_46	AC	593 ms 119,352 KB
testcase_47	AC	689 ms 210,400 KB
testcase_48	AC	762 ms 194,268 KB
testcase_49	AC	763 ms 212,728 KB
testcase_50	AC	728 ms 212,200 KB
testcase_51	AC	634 ms 216,260 KB
testcase_52	AC	597 ms 123,896 KB
testcase_53	AC	560 ms 116,908 KB
testcase_54	AC	677 ms 214,424 KB
testcase_55	AC	677 ms 195,112 KB
testcase_56	AC	594 ms 128,376 KB
testcase_57	AC	790 ms 237,756 KB
testcase_58	AC	676 ms 254,584 KB
testcase_59	AC	589 ms 127,996 KB
testcase_60	AC	753 ms 213,536 KB
testcase_61	AC	591 ms 157,676 KB
testcase_62	AC	706 ms 247,364 KB
testcase_63	AC	699 ms 237,780 KB
testcase_64	AC	637 ms 178,532 KB
testcase_65	AC	543 ms 113,512 KB
testcase_66	AC	605 ms 158,040 KB
testcase_67	AC	599 ms 132,576 KB
testcase_68	AC	555 ms 113,708 KB
testcase_69	AC	603 ms 137,904 KB
testcase_70	AC	672 ms 189,964 KB
testcase_71	AC	606 ms 179,448 KB
testcase_72	AC	666 ms 216,600 KB
testcase_73	AC	693 ms 239,308 KB
testcase_74	AC	669 ms 212,008 KB
testcase_75	AC	644 ms 212,548 KB
testcase_76	AC	623 ms 177,836 KB
testcase_77	AC	669 ms 236,472 KB
testcase_78	AC	829 ms 196,176 KB
testcase_79	AC	711 ms 254,772 KB
testcase_80	AC	681 ms 177,496 KB
testcase_81	AC	671 ms 236,456 KB
testcase_82	AC	693 ms 238,592 KB
testcase_83	AC	681 ms 177,412 KB
testcase_84	AC	626 ms 178,968 KB
testcase_85	AC	709 ms 214,192 KB
testcase_86	AC	674 ms 232,884 KB
testcase_87	AC	701 ms 211,640 KB
testcase_88	AC	668 ms 236,684 KB
testcase_89	AC	652 ms 163,284 KB
testcase_90	AC	674 ms 239,248 KB
testcase_91	AC	678 ms 238,764 KB
testcase_92	AC	679 ms 239,108 KB
testcase_93	AC	679 ms 246,260 KB
testcase_94	AC	660 ms 239,404 KB
testcase_95	AC	693 ms 238,476 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):
                e = ind(i,i*j)
                phi[i*j] *= pow(i,e-1)*(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):
        if data[i*j]:
            res += (i)*phi[j]*data[i*j]

print(res)

yukicoder

結果

テストケース

ソースコード