C++(clang++11) 解法, 执行用时: 445ms, 内存消耗: 66912K, 提交时间: 2021-04-30 20:19:45

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 5000001;
 
int p[MAXN], tot, f[2002];
long long mu[MAXN], ans;
bool chk[MAXN];
int n, m, K, pk[20], cntk;
map < pair < int, int >, long long > F;
map < int, long long > G;
 
inline void init()
{
	mu[ 1 ] = 1;
	for( int i = 2 ; i < MAXN ; i++ )
	{
		if( !chk[ i ] ) mu[ p[ ++tot ] = i ] = -1;
		for( int j = 1 ; i * p[ j ] < MAXN ; j++ )
		{
			chk[ i * p[ j ] ] = 1;
			if( i % p[ j ] ) mu[ i * p[ j ] ] = -mu[ i ];
			else break;
		}
	}
	for( int i = 2 ; i < MAXN ; i++ ) mu[ i ] += mu[ i - 1 ];
	for( int i = 1 ; i <= K ; i++ ) f[ i ] = f[ i - 1 ] + ( __gcd( i, K ) == 1 );
}
 
inline int cal(int x) { return x / K * f[ K ] + f[ x % K ]; }
 
inline long long get(int x)
{
	if( x < MAXN ) return mu[ x ];
	if( G.find( x ) != G.end() ) return G[ x ];
	long long ret = 1;
	int pos;
	for( int i = 2 ; i <= x ; i = pos + 1 )
	{
		pos = x / ( x / i );
		ret -= ( pos - i + 1 ) * get( x / i );
	}
	return G[ x ] = ret;
}
 
inline long long solve(int x, int y)
{
	if( !x ) return get( y );
	if( y <= 1 ) return y;
	if( F.find( make_pair( x, y ) ) != F.end() ) return F[ make_pair( x, y ) ];
	return F[ make_pair( x, y ) ] = solve( x - 1, y ) + solve( x, y / pk[ x ] );
}
 
int main()
{
	scanf( "%d%d%d", &n, &m, &K );
	init();
	int pos;
	for( int i = 1 ; p[ i ] <= K ; i++ ) if( K % p[ i ] == 0 ) pk[ ++cntk ] = p[ i ];
	for( int i = 1 ; i <= min( n, m ) ; i = pos + 1 )
	{
		pos = min( n / ( n / i ), m / ( m / i ) );
		ans += 1ll * ( solve( cntk, pos ) - solve( cntk, i - 1 ) ) * ( n / i ) * cal( m / i );
	}
	cout << ans << endl;
	return 0;
}