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

UVA – 1393 Highways(枚举包围盒大小,包围盒只有对角线穿过两个点)

2019年04月03日 ⁄ 综合 ⁄ 共 483字 ⁄ 字号 评论关闭
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn =305;
int m,n;
int g[maxn][maxn];
int gcd(int a,int b){
return b==0 ? a : gcd(b,a%b);
}
void init(){
  int lim = 300;
  for(int i=1;i<=lim;i++)
       for(int j=1;j<=lim;j++)
           g[i][j] = gcd(i,j);
}
int main()
{
    init();
    while(scanf("%d %d",&m,&n)==2){
           if(!n&&!m) break;
           LL res = 0;
           for(int a=1;a<m;a++)
              for(int b=1;b<n;b++){
                 if(g[a][b] > 1) continue;
                 res+=(m-a)*(n-b)-max(0,m-2*a)*max(0,n-2*b);
           }
           printf("%lld\n",res*2);
    }
    return 0;
}

抱歉!评论已关闭.