Java(javac 1.8) 解法, 执行用时: 107ms, 内存消耗: 15300K, 提交时间: 2020-10-15 18:05:02

import java.util.Scanner;

public class Main {
	static int[] euler = new int[1005];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		euler[1] = 1;
		for(int i=2;i<1005;i++) {
			if(euler[i]==0) {
				for(int j=i;j<1005;j+=i) {
					if(euler[j]==0) euler[j] = j;
					euler[j] -= euler[j]/i;
				}
			}
		}
		int c = sc.nextInt();
		for(int ci=1;ci<=c;ci++) {
			int n = sc.nextInt();
			int ans = 3;
			for(int i=2;i<=n;i++) {
				ans += euler[i]*2;
			}
			System.out.println(ci+" "+n+" "+ans);
		}
	}
}

C++14(g++5.4) 解法, 执行用时: 7ms, 内存消耗: 384K, 提交时间: 2020-05-31 10:18:42

#include<bits/stdc++.h>
using namespace std;
const int N=1E3+100;
int phi[N];
void Euler(int n) {
	for(int i=2; i<n; i++)phi[i]=i;
	for(int i=2; i<n; i++)
		if(phi[i]==i) {
			for(int j=i; j<n; j+=i)
				phi[j]=phi[j]/i*(i-1);
		}
}
int main() {
	Euler(N);
	int c,n;
	cin>>c;
	for(int i=1; i<=c; i++) {
		cin>>n;
		int d=0;
		for(int j=2; j<=n; j++)
			d+=phi[j];
		d*=2;
		d+=3;
		cout<<i<<" "<<n<<" " <<d<<endl;
	}
	return 0;
}

C++(clang++11) 解法, 执行用时: 3ms, 内存消耗: 516K, 提交时间: 2020-12-29 14:56:29

#include<stdio.h>
#define R 
int t,n,tot;
int phi[1005];
const int maxn=1000;
int main() {
	scanf("%d",&t);
	for(R int i=2; i<=maxn; ++i) {
		phi[i]=i;
	}
	for(R int i=2; i<=maxn; ++i) {
		if(phi[i]==i) {
			for(R int j=i; j<=maxn; j+=i) {
				phi[j]=phi[j]*(i-1)/i;
			}
		}
		phi[i]+=phi[i-1];
	}
	while(t--) {
		scanf("%d",&n);
		printf("%d %d %d\n",++tot,n,3+(phi[n]<<1));
	}
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 5ms, 内存消耗: 384K, 提交时间: 2022-08-03 20:13:31

#include<iostream>
using namespace std;
long long a[1010];
int main()
{
	for(int i=1;i<1010;i++)
	{
		a[i]=i;
	}
	for(int i=2;i<1010;i++)
	{
		if(a[i]==i)
		{
			for(int j=i;j<1010;j+=i)
			{
				a[j]=a[j]/i*(i-1);
			}
		}
	}
	for(int i=2;i<1010;i++)
	{
		a[i]=a[i]+a[i-1];
	}
	int n,g;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>g;
		cout<<i<<" "<<g<<" "<<a[g]*2+1<<endl;
	}
	return 0;
}