[数据结构与算法]2021蓝桥杯 直线（枚举，set去重）

直线

两个点(x1,y1)(x2,y2)确定的直线方程可以化为
(y1-y2)x-(x1-x2)y+y1(x1-x2)-(y1-y2)x1=0
即Ax+By+C=0的规范式
这样的好处在于不用除法，避免了浮点数精度的问题。
枚举范围内的所有点，保证y1>y2(或者保证y1<y2)，去掉x1=x2或者y1=y2的情况（最后直接在结果中加上）。

import java.util.*;


public class Main{
	public static int gcd2(int a,int b) {
		a=Math.abs(a);
		b=Math.abs(b);
		int min=a<b?a:b;
		int max=a>b?a:b;
		int r=max%min;
		while(r!=0) {
			max=min;
			min=r;
			r=max%min;
		}
		return min;
	}
	public static int gcd3(int a,int b,int c) {
		a=Math.abs(a);
		b=Math.abs(b);
		c=Math.abs(c);
		return gcd2(a,gcd2(b,c));
	}
	public static void main(String[] Args) {
		Scanner sc=new Scanner(System.in);
		Set<String> s=new HashSet<String>();
		int a,b,c,d;
		int m=20,n=21;
		for(int x1=0;x1<m;x1++) {
			for(int y1=0;y1<n;y1++) {
				//外面两层循环枚举第一个点
				for(int x2=0;x2<m;x2++) {
					for(int y2=0;y2<n;y2++) {
						//里面两层循环枚举第二个点
						//斜率为0和斜率不存在的情况单独加
						//y1>y2保证枚举的A的系数为正，就可以保证唯一
						if(x1==x2 || y1==y2 || y1<y2) {
							continue;
						}
						a=y1-y2;
						b=x1-x2;
						c=y1*(x1-x2)-(y1-y2)*x1;
						if(c==0) {
							d=gcd2(a,b);
							s.add(String.valueOf(a/d)+'-'+String.valueOf(b/d));
						}else {
							d=gcd3(a,b,c);
							s.add(String.valueOf(a/d)+'-'+String.valueOf(b/d)+'-'+String.valueOf(c/d));
						}
						
					}
					
				}
			}
		}
		System.out.println(s.size()+m+n);
		sc.close();
	}
}

答案 2430
枚举因子的时候到sqrt(n)结束，可以显著降低时间复杂度。

import java.util.*;


public class Main{
	public static long get(long item) {
		long ans=0;
		for(long i=1;i<=Math.sqrt(item);i++) {
		if(item%i==0) {
			if(i*i==item)
				ans++;
			else ans+=2;
		}
		}
		return ans;
	
	}
	public static void main(String[] Args) {
		Scanner sc=new Scanner(System.in);
		Set<Long> s=new HashSet<Long>();
		long x=2021041820210418L;
		long ans=0;
		for(long i=1;i<=Math.sqrt(x);i++) {
			if(x%i==0) {
				//分别统计i和x/i的分解个数
				if(i*i==x) {
					ans+=get(i);
				}else {
					ans+=get(i);
					ans+=get(x/i);
				}
			}
		}
		System.out.print(ans);
		sc.close();
	}
}