Java(javac 1.8) 解法, 执行用时: 589ms, 内存消耗: 24472K, 提交时间: 2021-03-11 14:24:39

import java.util.*;

public class Main
{

	static long n;
	static int mu[] = new int[1000100];
	static int s[] = new int[1000100];
	static int prim[] = new int[1000100];
	static int cnt = 0;

	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);
		while (s.hasNext())
		{
			n = s.nextLong();
			shai();
			long ans = 0;
			for (int i = 1; i <= n; i++)
			{
				for (int j = i; j <= n; j += i)
					ans += mu[i] * (n / i - j / i + 1) * g(j) + mu[i] * (j / i) * f(j);
			}
			System.out.println(ans);
		}
	}

	static void shai()
	{
		mu[1] = 1;
		for (int i = 2; i <= n; i++)
		{
			if (s[i] == 0)
			{
				prim[++cnt] = i;
				mu[i] = -1;
			}
			for (int j = 1; j <= cnt && prim[j] * i <= n; j++)
			{
				s[prim[j] * i] = 1;
				if (i % prim[j] == 0)
					break;
				mu[i * prim[j]] = -mu[i];
			}
		}
	}

	static int g(int x)
	{
		int mul = 1;
		while (x > 0)
		{
			mul *= x % 10;
			x /= 10;
		}
		return mul;
	}

	static int f(int x)
	{
		int ans = 0;
		while (x > 0)
		{
			ans += x % 10;
			x /= 10;
		}
		return ans;
	}

}

C++(clang++11) 解法, 执行用时: 317ms, 内存消耗: 8440K, 提交时间: 2020-11-28 13:45:50

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
int mu[1000100],s[1000100],prim[1000100];
ll cnt=0;
void shai()
{
	mu[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!s[i])
		{
			prim[++cnt]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=cnt&&prim[j]*(ll)i<=n;j++)
		{
			s[prim[j]*i]=1;
			if(i%prim[j]==0)
				break;
			mu[i*prim[j]]=-mu[i];
		}
	}
}
ll f(int p)
{
	ll ans=0;
	while(p)
	{
		ans+=p%10;
		p/=10;
	}
	return ans;
}
ll g(int p)
{
	ll ans=1;
	while(p)
	{
		ans*=p%10;
		p/=10;
	}
	return ans;
}
int main()
{
	cin>>n;
	shai();
	ll ans=0;
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j+=i)
		{
			ans+=mu[i]*1ll*(n/i-j/i+1)*g(j)+mu[i]*1ll*(j/i)*f(j);
		}
	printf("%lld\n",ans);
	return 0;
}