首页 > 代码库 > UVA 1393 Highways(数学思想)
UVA 1393 Highways(数学思想)
题意:给你n、m(n,m<=200),问你有多少条非水平、非垂直的直线有多少条经过至少两个点
题解:我们需要枚举的是只画一条线的矩形,对于大小a*b的矩形必须保证gcd(a,b)=1才能不重复
接着对于每个矩形可以放的位置有(n-a)(m-b)个,但是如果有矩形在某个矩形的左上方就会再次重复
因此只需要再减去max(0,n-2*a)*max(0,m-2*b)就好
import java.util.Scanner; public class Main{ static int Max=305; static int[][] gcd=new int[Max][Max]; static{ for(int i=1;i<Max;++i){ for(int j=1;j<Max;++j){ gcd[i][j]=Gcd(i, j); } } } public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n,m; while(sc.hasNext()){ n=sc.nextInt(); m=sc.nextInt(); if(n+m==0) break; System.out.println(Solve(n,m)); } } private static int Solve(int n, int m) { int res=0; for(int i=1;i<n;++i){ for(int j=1;j<m;++j){ if(gcd[i][j]==1){ int a1,a2; a1=(n-i)*(m-j); a2=Math.max(0, n-2*i)*Math.max(0, m-2*j); res+=a1-a2; //System.out.println(res); } } } return res*2; } private static int Gcd(int i, int j) { if(j==0) return i; else return Gcd(j, i%j); } }
UVA 1393 Highways(数学思想)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。