设一种方案里三角形上三个点的坐标分别为$(0,0),(-a,b),(c,d)$，则得到的平行四边形的面积为$ac+bd$。

设$d(n)$为$n$的约数个数，$D$为$d$的生成函数，则答案的生成函数$=D^2$。

先用线性筛$O(n)$求出$d$，再用FFT在$O(n\log n)$的时间内预处理出所有答案即可。

 

#include
     
      #include
      
       #include
       
        #define N 1048576using namespace std;typedef long long ll;int n=500000,d[N],g[N],i,j,p[N],tot,T,l,r,ans;bool v[N>>1];ll f[N];struct comp{  double r,i;comp(double _r=0,double _i=0){r=_r;i=_i;}  comp operator+(const comp x){return comp(r+x.r,i+x.i);}  comp operator-(const comp x){return comp(r-x.r,i-x.i);}  comp operator*(const comp x){return comp(r*x.r-i*x.i,r*x.i+i*x.r);}}a[N];const double pi=acos(-1.0);void FFT(comp a[],int n,int t){  for(int i=1,j=0;i
        
         >=1,~j&s;);    if(i
         
          f[ans])ans=l;  }  return 0;}