Chef Counting Matrices 矩阵

tilg

　　题目大意：给你一个2*2的矩阵的迹--n。让你求所有元素为正且行列式的值为正的情况数。
　　根据矩阵的概念可得：迹=a11+a22; 行列式的值=a11*a22-a12*a21>0
用dp表示两数乘积为i的情况数。sum表示乘积小于等于i的情况数总和。


　　对于n=2500，最大乘积MAX=n/2*n/2，预处理一下（开始i<N错了我好久）。最后枚举a11的&#20540;，a12=n-a11。求乘积小于a11*a12的情况总数即可。
　　

#include<stdio.h>
const int N=2501,MAX=N*N/4;
typedef long long LL;
int dp[MAX],sum[MAX];
void init(){
for(int i=1;i<MAX;i++){// i<N is wa
for(int j=1;j<MAX;j++){
if(i*j>MAX) break;
dp[i*j]++;
}
}
for(int i=1;i<MAX;i++){
sum=sum[i-1]+dp;
}
}
int main(){
init();
int tt,n;
scanf(&quot;%d&quot;,&tt);
while(tt--){
scanf(&quot;%d&quot;,&n);
LL ans=0;
for(int i=1;i<n;i++){//枚举a11
int mul=i*(n-i);//取值范围是1-n*n/4
ans+=(LL)sum[mul-1];
}
printf(&quot;%lld\n&quot;,ans);
}
}