C++ 解法, 执行用时: 551ms, 内存消耗: 8508K, 提交时间: 2021-05-21 18:43:07

#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 1e6;
int mu[N + 1], p[N + 1], v[N + 1];
ll getsqrt(ll n, ll d, ll x){
	ll l = 0, r = n, mid;
	while(l < r){
		mid = l + r + 1 >> 1;
		(__int128)d * d * (x * x + mid * mid) <= n * n ? l = mid : r = mid - 1;
	}return l;
} 
int main(){
	int n, i, j;ll k, ans;
	scanf("%d", &n);
	for(mu[1] = 1, i = 2;i <= n;i++){
		if(!v[i])mu[p[++p[0]] = i] = -1;
		for(j = 1;j <= p[0] && i * p[j] <= n;j++){
			v[i * p[j]] = 1;
			if(i % p[j])mu[i * p[j]] = -mu[i];
			else{
				mu[i * p[j]] = 0;
				break;
			}
		}
	}for(i = 1, ans = 0;i <= n;i++)if(mu[i]){
		for(j = 1, k = 0;j <= n / i;j++)k += getsqrt(n, i, j);
		ans += mu[i] * k;
	}printf("%lld", 4 * (ans + 1));
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 178ms, 内存消耗: 31708K, 提交时间: 2020-07-19 16:36:23

#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=1000005;

int n,len[N];
int prime[N][7];

void init(){
	for(int i=2;i<N;i++){
		if(!len[i]){
			for(int j=i;j<N;j+=i){
				prime[j][len[j]++]=i;
			}
		}
	}
}


int main(){
	init();
	scanf("%d",&n);
	long long ans=0;
	for(int i=1;i<n;i++){
		int y=sqrt((long long)n*n-(long long)i*i);
		ans+=y;
		
		for(int S=1;S<(1<<len[i]);S++){
			int cnt=0,sum=1;
			for(int j=0;j<len[i];j++){
				if(S&(1<<j)){
					cnt++;
					sum*=prime[i][j];
				}
			}
			if(cnt&1){
				ans-=y/sum;
			}else{
				ans+=y/sum;
			}
		}	
		
		
	}
	printf("%lld\n",ans*4+4);
	return 0;
}