程序员人生 网站导航

uva 1393 Highway

栏目:php教程时间:2016-11-19 14:13:03

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; }

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐