結果
問題 | No.2249 GCDistance |
ユーザー | chineristAC |
提出日時 | 2023-03-17 21:45:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,463 ms / 5,000 ms |
コード長 | 978 bytes |
コンパイル時間 | 168 ms |
コンパイル使用メモリ | 81,748 KB |
実行使用メモリ | 233,728 KB |
最終ジャッジ日時 | 2023-10-18 14:18:12 |
合計ジャッジ時間 | 30,575 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,321 ms
233,152 KB |
testcase_01 | AC | 2,369 ms
233,724 KB |
testcase_02 | AC | 2,356 ms
233,728 KB |
testcase_03 | AC | 2,377 ms
233,728 KB |
testcase_04 | AC | 2,295 ms
233,620 KB |
testcase_05 | AC | 2,463 ms
233,724 KB |
testcase_06 | AC | 2,365 ms
233,724 KB |
testcase_07 | AC | 2,349 ms
233,720 KB |
testcase_08 | AC | 2,266 ms
233,552 KB |
testcase_09 | AC | 2,351 ms
233,724 KB |
testcase_10 | AC | 2,339 ms
233,680 KB |
ソースコード
#ごめんなさいpypy遅くないです import sys,random,bisect from collections import deque,defaultdict from heapq import heapify,heappop,heappush from itertools import permutations from math import gcd,log input = lambda :sys.stdin.readline().rstrip() mi = lambda :map(int,input().split()) li = lambda :list(mi()) def brute(N): res = 0 for i in range(1,N+1): for j in range(i+1,N+1): if gcd(i,j) == 1: res += 1 return res M = 10**7 mebius = [1] * (M+1) phi = [i for i in range(M+1)] for p in range(2,M+1): if phi[p] == p: for k in range(p,M+1,p): mebius[k] *= -1 t = p*p for k in range(t,M+1,t): mebius[k] = 0 if mebius[p]!=0: t = mebius[p] for q in range(1,M//p+1): phi[q*p] += t * q for i in range(1,M+1): phi[i] += phi[i-1] for _ in range(int(input())): N = int(input()) res = N*(N-1) - (phi[N]-1) print(res)