uva 1393 Highway

发布时间：2020-12-13 21:16:19 所属栏目：PHP教程来源：网络整理

导读：Problem: 给定1个m*n的点阵，求最少穿过两个点的直线有多少条？ Solution: 把每条直线看成是1个盒子的对角线，那末我们可以枚举不同大小的盒子，找到盒子的不同位置，然后去除盒子在同1条直线上的情况。 1. 枚举盒子的左上角，对每个盒子有(m-a)(n-b)种情况

Problem:
给定1个m*n的点阵，求最少穿过两个点的直线有多少条？
Solution:
把每条直线看成是1个盒子的对角线，那末我们可以枚举不同大小的盒子，找到盒子的不同位置，然后去除盒子在同1条直线上的情况。
1. 枚举盒子的左上角，对每个盒子有(m-a)(n-b)种情况。
2. 左上角有盒子致使对角线重复的有(m⑵a)(n⑵b)种情况(不同等于两边相加，由于盒子内也能够有顶点)。
3. 终究乘2，由于有两条对角线。
note:
1. 互素不1定就非得用欧拉定理，要灵活使用。
2. 要把模型正确的转换和抽象，方便理解。
3. 对反复使用的元素要打表存储起来。

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;

const int maxs = 300;
bool g[maxs+1][maxs+1];

int gcd(int a,int b){
    a = abs(a);  b = abs(b);
    while(b != 0){
        int t = a%b;
        a = b;
        b = t;
    }
    return a;
}

void make_phi_table(){//0互素
    int m,n;
    memset(g,0,sizeof(g));
    for(int i = 1; i <= maxs; ++i){
        for(int j = i; j <= maxs; ++j){
            if(g[i][j]==0 && gcd(i,j)==1){
                m = i+i;  n = j+j;
                while(m<=maxs && n<=maxs){
                    g[m][n] = g[n][m] = 1;
                    m += i;  n += j;
                }
            }
        }
    }
}

int main() {
  int n,m;
  make_phi_table();

  while(cin >> n >> m && n) {
    int ans = 0;
    for(int a = 1; a <= m; a++)
      for(int b = 1; b <= n; b++)
        if(g[a][b] == 0) {
          int c = max(0,m-2*a) * max(0,n-2*b);
          ans += (m-a)*(n-b) - c;
        }
    cout << ans*2 << "n";
  }
  return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!