首页 > 代码库 > UVALive - 3295
UVALive - 3295
给定n行m列个正方形,求可以组成多少个三角形。
如1×2,有18个。
总的点有N个,那个答案就是C(N,3),然后减去横向、竖向、斜向的三点共线的个数即可,斜线三点共线等价于所枚举的矩形的长宽成倍数关系,即gcd不为1。
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <algorithm> 5 #include <string> 6 #include <queue> 7 #include <vector> 8 #include <set> 9 #include <map> 10 #define ll long long 11 #define INF 0x3f3f3f3f 12 #define lowvit(x) x&(-x) 13 #define N 1010 14 #define M 110 15 using namespace std; 16 ll gcd(ll a, ll b) { 17 return b ? gcd(b, a%b): a; 18 } 19 int main() { 20 ios::sync_with_stdio(false); 21 ll a, b; 22 int k = 1; 23 while(cin>>a>>b) { 24 if(a==0&&b==0)break; 25 ll n = (a+1)*(b+1); 26 ll sum1 = n*(n-1)*(n-2)/6; 27 ll sum2 = (a+1)*(b+1)*(b)*(b-1)/6 + (b+1)*(a+1)*a*(a-1)/6; 28 ll sum3 = 0; 29 for(int i = 2; i <= a; i ++) { 30 for(int j = 2; j <= b; j ++) { 31 sum3 += (gcd(i,j)-1)*(a-i+1)*(b-j+1); 32 } 33 } 34 ll ans = sum1 - sum2 - 2*sum3; 35 printf("Case %d: %lld\n",k++,ans); 36 } 37 return 0; 38 }
UVALive - 3295
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。