现在的位置: 首页 > 综合 > 正文

3505: [Cqoi2014]数三角形

2018年04月25日 ⁄ 综合 ⁄ 共 465字 ⁄ 字号 评论关闭
#include<iostream>
#include<cstdio>
using namespace std;
int m,n;
long long f[1002*1002][4],ans,tmp;
void calc(){
	f[0][0]=1;
	for(int i=1;i<=m*n;i++){
		f[i][0]=1;
		for(int j=1;j<=3;j++)
			f[i][j]=f[i-1][j-1]+f[i-1][j];
	}
}
inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
void solve(){
	ans=f[m*n][3]-f[n][3]*m-f[m][3]*n;
	for(int i=1;i<n;i++)
		for(int j=1;j<m;j++){
			tmp=gcd(i,j)+1;
			if(tmp>2)ans-=(tmp-2)*2*(n-i)*(m-j);
		}
}
int main(){
	scanf("%d%d",&m,&n);
	m++;n++;calc();solve();
	printf("%lld",ans);
	return 0;
}

抱歉!评论已关闭.