欧拉函数解法与半暴力解法

方法一：求互质数量解法

本题目重点需要把坐标数据的关系找到，先分析一半区域，所找点一定是一对互质的

根据所找点性质就会想到利用欧拉函数来求

注意结果需要加上 (1,0) 和 (0,1) ，同时(1,1)不能翻倍

python版本

def getPrimes(n):
    phi[1] = 1 #默认0与1互质
    vis = [False]*(N + 1)
    for i in range(2,n+1):
        if vis[i] == False:
            primes.append(i)
            phi[i] = i - 1
        j = 0
        while primes[j]*i <= n:
            vis[primes[j]*i] = True
            phi[primes[j]*i] = (primes[j] - 1)*phi[i]
            if i % primes[j] == 0:
                phi[primes[j]*i] = primes[j]*phi[i]
                break
            j += 1

N = 1010
phi = [0]*(N + 1)
primes = []
getPrimes(N)

pre = [0]*(N+1)
for i in range(1,N+1):
    pre[i] = pre[i - 1] + phi[i]

t = int(input())
for i in range(t):
    n = int(input())

    print(i + 1,n,pre[n]*2 + 1)

方法二：暴力二维前缀和解法(看数据量)

将所有互质数塞进二维前缀和里，结果利用二位前缀和计算区域内互质数个数

python版本

def exGcd(a,b):
    if b== 0:
        return 1,0,a
    x,y,gcd = exGcd(b,a%b)

    return y , x - a // b * y ,gcd



N = 1010
board = [[0]*(N) for i in range(N)]
for i in range(N):
    for j in range(N):
        x,y,gcd = exGcd(i,j)
        if gcd == 1:
            board[i][j] = 1

pre = [[0]*(N) for i in range(N)]
for i in range(1,N):
    for j in range(1,N):
        pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + board[i][j]

t = int(input())
for i in range(t):
    n = int(input())
    print(i+1,n,pre[n][n]+2)