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;
}
下一篇 五，建造者模式
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
