CQOI2014 数三角形

首先一看题，先容斥一波，求出网格内选三个点所有的情况，也就是C（n*m，3）;然后抛出行里三点共线的方案数：C(n，3)*m;

同理就有列中三点共线的方案数：n*C(m，3)

还要刨去对角线的方案数，由于gcd（i，j）-1就是这条线（（i，j）与原点的连线）的方案数，然后这样的线斜着因为方向不同就要*2 然后这样的线在整个网格中总共有(m-j+1)*(n-i+1)种所以求出公式C(n*m,3)-n*C(m,3)-m*C(n,3)-∑(m-j+1)*(n-i+1)*(gcd(i,j)-1)*2,完结！

 

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #define LL long long 7 using namespace std; 8 LL n,m,ans; 9 LL gcd(LL x,LL y){
    return y==0?x:gcd(y,x%y);}10 int main()11 {12     scanf("%lld %lld",&n,&m);13     n++,m++;14     for(int i=1;i<=n;i++)15         for(int j=1;j<=m;j++)16         {17             ans+=(n-i)*(m-j)*(gcd(i,j)-1)*2;18             //cout<
           <<" "<
            
             <<" "<<(n-i+1)*(m-j+1)*(gcd(i,j)-1)*2<
            
          
         
        
       
      

T2方

这道题做的我整个人都方了，然后，我到现在都没有过这道题，因为我的程序使用了太多的stl，然后躺尸，TLE没办法，本人也很想写这道题的题解，本人对着道题的领会也很深刻，但是没有AC，整个人都没有底气，所以我的博客里就先挖个坑，这个坑也是以后要填的，没事，终究会AC的！

（本杂题集根据个人进度选更！）