Problem:


Problem F: Farey Sequence

slipは数字を眺めるのが好きである。
ファイルをダウンロードしているときの、残り時間を眺めているだけで、時間を潰せるほどである。
そんなslipが友人から面白い数列を教えられた。
その数列の定義は以下のとおりである。

一般項をFnと表わす。
Fnとは、n以下の分母を持つ0以上1以下のすべての約分された分数(既約分数)を小さな順から並べたものである。
ただし、整数0、1はそれぞれ分数0/1、1/1として扱われる。

つまりF3は、

F3 = (0/1, 1/3, 1/2, 2/3, 1/1)

のように表される。

F5であれば

F5 = (0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1)

と表される。

slipはこの数列にすぐにのめり込んだ。
しかしこの数列を眺めていても、なかなか特徴がつかめなかった。
特徴をつかむためにまずは各項の項数がいくつあるのか調べようと思ったが、
増え方の規則がわからず、自力で理解することを断念した。

そこで、
勝手に友人と思っているあなたに、指定した項にどれだけの項数があるのかを聞くことにした。
あなたの仕事は、与えられた項における項数を求めることである。

Input

入力は以下の形式で与えられる。

t
n1
...
ni
...
nt

t(1 ≤ t ≤ 10000)はテストケースの数である。
ni(1 ≤ ni ≤ 1000000)は与えられた項の番号である。

Output

各テストケースごとに、項数を1行に表示せよ。

Sample Input

2
3
5

Output for Sample Input

5
11



Sample input:
2
3
5


Sample output:
5
11

Submission status: Wrong Answer

Solution code:
MAX_N = 10**6+1
over = [0] * MAX_N
for i in xrange(2, MAX_N/2):
    for j in xrange(i+i, MAX_N, i):
        over[j] += (i-1)-over[i]
ans = [0] * MAX_N
ans[0] = 1
ans[1] = 2
for i in xrange(2,MAX_N):
    ans[i] = ans[i-1] + (i - 1) - over[i]
for _ in xrange(input()):
    print ans[int(raw_input())]

Submission status: Wrong Answer

Solution code:
count = range(1000001) 
for i in range(2, 1000001):
    if count[i] != i:
        continue
    n = i * 2
    while n <= 1000000:
        count[n] -= (i - 1) 
        n += i

ret = [0] * 1000001
ret[1] = 2
for i in range(2,1000001):
    ret[i] += count[i] + ret[i-1] - 1

t = int(raw_input())
for i in range(t):
    print ret[int(raw_input())]

Submission status: Accepted

Solution code:
MAX_N = 10**6+1
over = [0] * MAX_N
for i in xrange(2, MAX_N):
    for j in xrange(i+i, MAX_N, i):
        over[j] += (i-1)-over[i]
ans = [0] * MAX_N
ans[0] = 1
ans[1] = 2
for i in xrange(2,MAX_N):
    ans[i] = ans[i-1] + (i - 1) - over[i]
for _ in xrange(input()):
    print ans[int(raw_input())]

Submission status: Accepted

Solution code:
MAX_N = 10**6+1
over = [0] * MAX_N
for i in xrange(2, MAX_N/2+1):
    for j in xrange(i+i, MAX_N, i):
        over[j] += (i-1)-over[i]
ans = [0] * MAX_N
ans[0] = 1
ans[1] = 2
for i in xrange(2,MAX_N):
    ans[i] = ans[i-1] + (i - 1) - over[i]
for _ in xrange(input()):
    print ans[int(raw_input())]

Submission status: Accepted

Solution code:
count = range(1000001) 
for i in range(2, 500001):
    n = i * 2
    while n <= 1000000:
        count[n] -= (count[i] - 1) 
        n += i

ret = [0] * 1000001
ret[1] = 2
for i in range(2,1000001):
    ret[i] += count[i] + ret[i-1] - 1

t = int(raw_input())
for i in range(t):
    print ret[int(raw_input())]

Submission status: Accepted

Solution code:
count = range(1000001) 
for i in xrange(2, 500001):
    n = i * 2
    while n <= 1000000:
        count[n] -= (count[i] - 1) 
        n += i

ret = [0] * 1000001
ret[1] = 2
for i in xrange(2,1000001):
    ret[i] += count[i] + ret[i-1] - 1

t = int(raw_input())
for i in xrange(t):
    print ret[int(raw_input())]

Submission status: Accepted

Solution code:
count = range(1000001) 
for i in xrange(2, 500001):
    for n in xrange(i*2, 1000001, i):
        count[n] -= (count[i] - 1) 
 
count[1] = 2
for i in xrange(2, 1000001):
    count[i] += count[i-1]

t = int(raw_input())
for i in xrange(t):
    n = int(raw_input())
    print count[n] - n + 1

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def primes_for(n):
   is_prime = [True] * (n + 1)
   is_prime[0] = False
   is_prime[1] = False
   for i in range(2, n + 1):
       for j in range(i * 2, n + 1, i):
           is_prime[j] = False
   return [i for i in range(n + 1) if is_prime[i]]

def totient(n):
  res = n
  for i in range(2, int(n**(1/2))+1):
    if n % i == 0:
      res = res / i*(i-1)
      while n % i == 0:
        n /= i
  if n != 1:
    res = res / n * (n-1)
  return res

def totient_list(n):
  euler = list(range(n+1))
  for i in range(2, n+1):
    if euler[i] == i:
      for j in range(i, n+1, i):
        euler[j] = euler[j] * (i-1) // i

  return euler

t = INT()
n = [INT() for _ in range(t)]

F = totient_list(10**6)
F[0] = 1
F = list(accumulate(F))

print("\n".join(map(str, [F[x] for x in n])))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = 1000001
table = list(range(N+1))
for i in range(2, N+1):
    # 各素数から、自分の倍数になる数に、オイラーのファイ関数を掛け込んでいく
    if table[i] == i:
        for j in range(i, N+1, i):
            table[j] *= 1 - 1/i

# 0/0の分を入れる
table[0] = 1
ans = list(accumulate(table))
for i in range(INT()):
    a = INT()
    print(int(ans[a]))

Submission status: Accepted

Solution code:
def get_prime_set(ub):
    from itertools import chain
    from math import sqrt

    if ub < 4:
        return ({}, {}, {2}, {2, 3})[ub]

    ub, ub_sqrt = ub+1, int(sqrt(ub))+1
    primes = {2, 3} | set(chain(range(5, ub, 6), range(7, ub, 6)))
    du = primes.difference_update
    for n in chain(range(5, ub_sqrt, 6), range(7, ub_sqrt, 6)):
        if n in primes:
            du(range(n*3, ub, n*2))

    return primes

def get_totient_count_range(ub, prime_set):
    ub, totient_count = ub+1, list(range(ub+1))

    for prime in prime_set:
        totient_count[prime] -= 1
        for m in range(prime*2, ub, prime):
            totient_count[m] = totient_count[m] * (prime-1) // prime
    return totient_count


import sys
from itertools import accumulate
ub = 10**6
primes = get_prime_set(ub)
a = get_totient_count_range(ub, primes)
a[1] = 2
a = list(accumulate(a))
input()
print(*(a[int(n)] for n in sys.stdin), sep="\n")

Submission status: Runtime Error

Solution code:
p = [1] * 1000001
for i in range(3, 1001, 2):
    if p[i] == 0:
        continue
    for j in range(2, 1000001/i):
        p[i*j] = 0

t = int(raw_input())
for i in range(t):
    n = int(raw_input())
    res = n * (n-1) / 2 + 2
    for j in range(2, n+1):
        if p[j] == 1:
            res -= (n / j - 1) * (j - 1)
    print res

Submission status: Runtime Error

Solution code:
p = [1] * 1000001
for i in range(2, 1001):
    if p[i] == 0:
        continue
    for j in range(2, 1000001/i):
        p[i*j] = 0

t = int(raw_input())
for i in range(t):
    n = int(raw_input())
    res = n * (n-1) / 2 + 2
    for j in range(2, n+1):
        if p[j] == 1:
            res -= (n / j - 1) * (j - 1)
    print res

Submission status: Runtime Error

Solution code:
p = [1] * 1000001
for i in range(2, 1001):
    if p[i] == 0:
        continue
    for j in range(2, 1000000/i+1):
        p[i*j] = 0

t = int(raw_input())
for i in range(t):
    n = int(raw_input())
    res = n * (n-1) / 2 + 2
    for j in range(2, n+1):
        if p[j] == 1:
            res -= (n / j - 1) * (j - 1)
    print res