C++14(g++5.4) 解法, 执行用时: 563ms, 内存消耗: 488K, 提交时间: 2019-05-11 21:46:45

#include<bits/stdc++.h>
using namespace std;
int n,s;double e=(1+sqrt(5))/2;
int main(){
    cin>>n;
    for(int q=1;q*q<=n;q++)
        for(int p=q;p<=q*e;p++)
            if(__gcd(p,q)==1) s+=n/p/p;
    cout<<s;
}

C++11(clang++ 3.9) 解法, 执行用时: 521ms, 内存消耗: 608K, 提交时间: 2019-05-12 12:13:46

#include<bits/stdc++.h>
using namespace std;
int n,s;double e=(1+sqrt(5))/2;
int main(){
    cin>>n;
    for(int q=1;q*q<=n;q++)
        for(int p=q;p<=q*e;p++)
            if(__gcd(p,q)==1) s+=n/p/p;
    cout<<s;
}