洛谷P3166 数三角形 [CQOI2014] 数论
正解:数论
解题报告:
很久以前做的题了呢,,,回想方法还想了半天QAQ
然后写这题题解主要是因为看到了好像有很新颖的法子,就想着,学习一下趴,那学都学了不写博客多可惜
首先港下最常规的方法趴QAQ
umm常规方法的话做过了还是比较容易想到的QAQ
就是,首先总共有C(n*m,3)个方案
最好想的是减去横着的和竖着的,就是n*C(m,3)+m*C(n,3)
然后斜着的我是用向量理解的,就是说把斜率理解成向量这么枚举,就过去了
over
代码是很久以前的了,丑陋快读+没有rg+没有il+没有printf,,,懒得改了凑合着看TT
#include<bits/stdc++.h> using namespace std; long long read() { char ch=getchar();long long x=0; while(ch>'9' || ch<'0')ch=getchar(); while(ch<='9' && ch>='0')x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar(); return x; } int main() { long long n=1+read(),m=1+read(),ans; ans=(long long)(n*m)*(n*m-1)*(n*m-2)/6-(long long)m*n*(n-1)*(n-2)/6-(long long)n*m*(m-1)*(m-2)/6; for(int i=1; i<n; i++)for(int j=1; j<m; j++)ans-=(n-i)*(m-j)*(__gcd(i,j)-1)*2; cout<<ans; return 0; }
然后除此之外还有,矩阵的完全覆盖,有时间再理解QAQ