code chef：Counting Matrices题解

code chef：Counting Matrices题解2015-02-25题目：给定一个数值，找出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;}}

From：csdn博客靖心