Problem 504

504.c

#include <tgmath.h>
#include <stdio.h>
#include <stdlib.h>

// 20s

// Euclidean Algorithm
int gcd(int x, int y){
	if(y < 1) exit(0);  // error
	int z;
	if(x < y){
		z = x;
		x = y;
		y = z;
	}
	if(x % y == 0) return y;
	return gcd(y, x % y);
}

int is_square(int a, int b, int c, int d){
	int lp_contains = ((a+c)*(b+d)/2) - (gcd(a,b) + gcd(b,c) + gcd(c,d) + gcd(d,a)) / 2 + 1;
	return pow((int)sqrt(lp_contains), 2) == lp_contains;
}
int main(){
	int m = 100;
	// printf("input m: "); scanf("%d", &m);
	int lp_square = 0; // answer
	for(int a = 1; a <= m; a++){
		for(int b = 1; b <= m; b++){
			for(int c = 1; c <= m; c++){
				for(int d = 1; d <= m; d++){
					if(is_square(a, b, c, d)) lp_square++;
				}
			}
		}
	}
	printf("answer: %d\n", lp_square);
}

504.rb

# Problem 504
# 1[m]28[s]

# def get_area(a, b, c, d)
#   return (a+c) * (b+d) / 2
# end

# def get_LP_side(a, b, c, d)
#   return a.gcd(b) + b.gcd(c) + c.gcd(d) + d.gcd(a)
# end

# Pick's theorem
# def get_LP(area, lp_side)
#   return area - lp_side/2 + 1
# end

def is_square(a, b, c, d)
  lp_contains = ((a+c)*(b+d)/2) - (a.gcd(b) + b.gcd(c) + c.gcd(d) + d.gcd(a)) / 2 + 1
  return Math.sqrt(lp_contains).to_i ** 2 == lp_contains
end

m = 100
# print 'input m: '
# m = gets.to_i;
lp_square = 0  # answer
1.upto(m){|a| 1.upto(m){|b| 1.upto(m){|c| 1.upto(m){|d| lp_square += 1 if is_square(a,b,c,d) } } } }
puts "#{lp_square} quadrilaterals strictly contain a square number of lattice points in m = #{m}"

504

文法を学ぶことも兼ねてRubyで最初に作成した。アルゴリズムは変えずにCで実装したところ，実行時間はおよそ 2/9 になった。

四角形ABCDに含まれる格子点を求める際ピックの定理を用いた。
完全に四角形の内部に含まれる格子点を求めるには，面積とABCDの辺上の格子点の数を求めれば良い。
辺上の格子点の数を求めるのに，最大公約数を用いた。