code chef
题目：给定一个数值，找出2*2矩阵的对角和等于N(N<2500)和行列式大于0的个数。这里是考数学知识了，程序不难，不过要精确计算好却也不容易。
最原始的程序，但是会超时：
void CountingMatrices()
{
int T = 0, N = 0;
cin>>T;
while (T--)
{
cin>>N;
long long ans = 0;
for (int i = 1; i < N; i++)
{
int a = i, b = N-i;
for (int d = 1; d < a*b; d++)//这里是d<a*b
{
int c = 1;
for ( ; c * d < a*b; c++) ;
ans += c-1;//这里要-1，数学要非常精确，不能差分毫！
}
}
cout<<ans<<endl;
}
}
优化程序,利用数学公式，有pairsOfNum函数实现：小于等于N的两个整数相乘的配对整数有多少对？推导这个公式有点麻烦。
Codechef上显示这些easy的题目牵涉到数学就不容易了。
int pairsOfNum(int N)
{
int ans = 0;
int sq = (int)sqrt(double(N));
for (int i = 1; i <= sq; i++)
{
ans += N/i;
}
ans = ans*2 - sq*sq;
return ans;
}
void CountingMatrices()
{
int T = 0, N = 0;
cin>>T;
while (T--)
{
cin>>N;
long long ans = 0;
for (int i = 1; i <= (N>>1); i++)
{
ans += pairsOfNum(i*(N-i) - 1);
}
ans <<= 1;
if (N%2 == 0) ans -= pairsOfNum((N>>1)*(N>>1)-1);
cout<<ans<<endl;
}
}
页:
[1]