C++ 解法, 执行用时: 3ms, 内存消耗: 376KB, 提交时间: 2020-10-02

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
set<int> S;
int n;
int main()
{
    scanf("%d",&n);
    int res=1LL*n*(n*2-1)%mod;
    for(int i=2; i*i<=n; i++)
    {
        if(S.find(i)!=S.end())
            continue;
        long long temp=i;
        int cnt=0;
        while(temp<=n)
        {
            S.insert(temp);
            temp=temp*i;
            cnt++;
        }
        for(int i=1; i<=cnt; i++)
        {
            for(int j=i+1; j<=cnt; j++)
            {
                res=(res+n/(j/__gcd(i,j))*2LL)%mod;
            }
        }
    }
    printf("%d\n",res);
    return 0;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 380KB, 提交时间: 2019-02-28

// diL 等式左值底数， diL 等式右值底数
// ciL 等式左值次数， ciR 等式右值次数
// 1-n的数每一个数i都对应着一堆以之为底的1-n的数，有di = i^ci
// 对于每一个数，分两种情况：
// 1.diL==diR，这种情况共有n*n (对应1)+n*(n-1) (对应2-n)种情况
// 2.diL != diR, 遍历左右值即可，对于一对diL,diR有n / (ciR / (ciR和ciL的公约数)) * 2种情况
// 这里n / (ciR / (ciR和ciL的公约数))求的是i在1-n范围时，i ciL/ciR为正整数的个数,
// 这里对于ciR的所有因子，一部分由ciL(也就是二者的最大公约数)提供，一部分由i提供。
#include <bits/stdc++.h>

using namespace std;
const int mod = 1e9+7;


unsigned int gcd(unsigned int i, unsigned j) {
	unsigned int res = j % i;
	while(res) {
		j = i;
		i = res;
		res = j % i;	
	}
	return i;
}

int main() {
	unsigned long long n;
	cin >> n;
    
    set<unsigned long long> sDis;
    
	unsigned int index = 2;
	unsigned long long count = 1 * (n * (n - 1) + n * n) % mod;
	while(index * index <= n) {
        
		unsigned long long diL = index;
		if(sDis.find(diL) != sDis.end()) {
            index++;
            continue;
        }
        
        unsigned long long tmp = index;
        while(tmp <= n) {
        	sDis.insert(tmp);
        	tmp *= index;
        }
		
		unsigned int ciL = 1;
		while(diL <= n) {
            unsigned ciR = ciL + 1;
            unsigned diR = diL * index;
            while(diR <= n) {
            	count = (count + (n / (ciR / gcd(ciL,ciR)) * 2)) % mod;	
            	ciR++;
            	diR = diR * index;
            }
			ciL++;
			diL = diL * index;
		}
		index++;
	}
	cout << count <<endl;
}