uva 1393 Highway

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

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » uva 1393 Highway

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡