题解 CF236B 【Easy Number Challenge】

原题

此题一个暴力就可以过了。

看着别的大佬不加记忆化吸口氧就过了，而我的却死活TLE

可能因为我人丑常数大？

注意到i*j*k的值会出现重复，所以考虑记忆化。

时间复杂度\(O(n^3\sqrt n)\)，跑得飞快

代码

const int N = 1e6 + 10,M = 1073741824;
int a,b,c;
int ans = 0;
int mry[N];
int d(int i , int j , int k)
{
	int n = i * j * k;
	if( !mry[n] ) // 未被记忆化过
	{
		int sum = 0;
		for(int i = 1;i * i <= n;i++) // 统计因数个数
			if(n % i == 0)
				if(i * i == n)
					++sum; // n有一个因数i
				else
					sum += 2; // n有两个因数i,n/i
		mry[n] = sum; // 记忆化
	}
	return mry[n];
}
int main()
{
	cin >> a >> b >> c;
	for(int i = 1;i <= a;i++) // 大力三重循环！
		for(int j = 1;j <= b;j++)
			for(int k = 1;k <= c;k++)
				ans = ( ans + d(i , j , k) ) % M;
	cout << ans << endl;
    return 0;
}