diff options
Diffstat (limited to 'euler504.c')
-rw-r--r-- | euler504.c | 73 |
1 files changed, 73 insertions, 0 deletions
diff --git a/euler504.c b/euler504.c new file mode 100644 index 0000000..3a7d0da --- /dev/null +++ b/euler504.c @@ -0,0 +1,73 @@ +#include <stdio.h> +#include <string.h> +#include <math.h> + +int inside[101][101]; + +int __inside(int a, int b) +{ + int count = 0; + /* y = -a/b * x + a */ + for (int i = 1; i < b; i++) { + int t = a - (i * a) / b - 1; + if (t > 0) + count += t; + } + return count; +} + +void init() +{ + for (int i = 1; i <= 100; i++) { + for (int j = i; j <= 100; j++) { + inside[i][j] = __inside(i, j); + } + } +} + +int ninside(int a, int b) +{ + if (a <= b) + return inside[a][b]; + else + return inside[b][a]; +} + +int issqr(int x) +{ + int sx = sqrt(x); + if (sx * sx == x) + return 1; + else + return 0; +} + +int main() +{ + int a, b, c, d; + int m; + int nsqr = 0; + init(); + scanf("%d", &m); + for (a = 1; a <= m; a++) { + for (b = 1; b <= m; b++) { + for (c = a; c <= m; c++) { + for (d = b; d <= m; d++) { + int count = ninside(a, b) + ninside(a, d) + + ninside(c, b) + ninside(c, d) + + a + b + c + d - 3; + if (issqr(count)) { + if (a == c && b == d) { + nsqr++; + } else if (a == c || b == d) { + nsqr += 2; + } else { + nsqr += 4; + } + } + } + } + } + } + printf("%d\n", nsqr); +} |