題目大意:給一張m*n的網格,問這裡面以網格為頂點的三角形有多少個。
思路:數學題。首先算出所有互不相同的三點對,然後減掉其中三個點在一個直線上的點對就行了。注意答案開long long。
CODE:
#include#include #include #include using namespace std; int m,n; int Gcd(int x,int y); int main() { cin >> m >> n; long long ans = (m + 1) * (n + 1); ans = ans * (ans - 1) * (ans - 2) / 6; for(int i = 0;i <= m; ++i) for(int j = 0;j <= n; ++j) { if(i == 0 && j == 0) continue; int x = Gcd(i,j); ans -= (x - 1) * (m - i + 1) * (n - j + 1) * (i * j ? 2:1); } cout << ans << endl; return 0; } int Gcd(int x,int y) { return y ? Gcd(y,x%y):x; }