首页 > 代码库 > zoj 3647 Gao the Grid
zoj 3647 Gao the Grid
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4837
先求出从所有点随机找出三个点的组合数,然后去掉共线的,平行好去掉,斜线就需要枚举矩形,也就是枚举两个端点形成向量。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 1000 5 #define ll long long 6 using namespace std; 7 8 ll c[maxn][maxn]; 9 int n,m;10 ll gcd(ll a,ll b)11 {12 if(b==0) return a;13 else return gcd(b,a%b);14 }15 16 ll cnr(int n,int r)17 {18 if(n<r)return 0;19 if(n-r<r)r=n-r;20 int i,j;21 ll ret=1;22 for(i=0,j=1;i<r;i++)23 {24 ret*=(n-i);25 for(;j<=r&&ret%j==0;j++)ret/=j;26 }27 return ret;28 }29 30 31 int main()32 {33 while(scanf("%d%d",&n,&m)!=EOF)34 {35 ll ans=cnr((n+1)*(m+1),3);36 if(n+1>=3)37 ans-=(m+1)*cnr(n+1,3);38 if(m+1>=3)39 ans-=(n+1)*cnr(m+1,3);40 for(int i=2; i<=n; i++)41 {42 for(int j=2; j<=m; j++)43 {44 if(gcd(i,j)-1)45 {46 ans-=(gcd(i,j)-1)*(n-i+1)*(m-j+1)*2;47 }48 }49 }50 printf("%lld\n",ans);51 }52 return 0;53 }
zoj 3647 Gao the Grid
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。