首页 > 代码库 > BZOJ 3505 数三角形
BZOJ 3505 数三角形
枚举i,j相当于枚举两点且确定里面还有整点。好巧啊。。。。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 1050 using namespace std; long long n,m,c[maxn*maxn][4]; long long gcd(long long a,long long b) { if (b==0) return a; return gcd(b,a%b); } void get_table() { c[0][0]=1; for (long long i=1;i<=(n+1)*(m+1);i++) { c[i][0]=1; for (long long j=1;j<=3;j++) c[i][j]=c[i-1][j]+c[i-1][j-1]; } } long long get_ans() { long long ret=0; for (long long i=1;i<=n;i++) for (long long j=1;j<=m;j++) { long long d=gcd(i,j); if (d!=1) ret+=(d-1)*(n-i+1)*(m-j+1); } return 2*ret; } int main() { scanf("%lld%lld",&n,&m); get_table(); printf("%lld\n",c[(n+1)*(m+1)][3]-(m+1)*c[n+1][3]-(n+1)*c[m+1][3]-get_ans()); return 0; }
BZOJ 3505 数三角形
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。