d903: 數學達人

2021-06-06 15:41:16 +0800 CST Tags: math

出處：https://zerojudge.tw/ShowProblem?problemid=d903
提交：https://zerojudge.tw/Submissions?problemid=d903&account=allllllan123456

問題：給定一張 n x n 的方格紙 (每邊有 n 個點、n-1 個間隔)，請問有幾個不同的正方形 (包含歪斜的) 它們的頂點都會落在格子點上？

解法：參考資料所寫的解法非常精簡扼要！如果我們把所有可能的正方形分成正常 (四邊皆與方格紙的邊平行)、歪斜 (四邊不與方格紙的邊平行) 兩部分，那麼很容易可以知道每個歪斜的正方形必定會外接一個唯一存在的正常正方形，只要知道每個不同的正常正方形會內接幾個歪斜正方形，就能清楚加總起來。那底線部分的答案便可以從參考資料的附圖清楚得到，一個邊長為 k 個間隔的正常正方形會包含它自己以及 k-1 個內接的歪斜正方形，而這張方格紙上有 $(n-1)^2$ 個邊長為間隔 1 的正常正方形、有 $(n-2)^2$ 個邊長為間隔 2 的正常正方形依此類推，到有 $1$ 個邊長為間隔 n-1 的正常正方形，於是全部的正方形個數便是 $\displaystyle\sum_{k=1}^{n-1}(n-k)^2\cdot k=\frac{n^2\ (n^2-1)}{12}$。但這題的實作有一個需要注意的地方，就是輸入上限 n=100000 會讓 $n^2$ $(n^2-1)$ 超過 unsigned long long 的上限，因此我們必須先對分子的左右兩邊 $n^2$、$(n^2-1)$ 盡可能地把能除的質因數都先除掉，再相乘，這樣子就能避免掉溢位的問題。

附註：
[1] https://home.gamer.com.tw/creationDetail.php?sn=4560510

 1#include <bits/stdc++.h>
 2using namespace std;
 3
 4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
 5    long long n, p, q;
 6    while (cin >> n) {
 7        p = n*n;
 8        q = n*n - 1;
 9        (p%2 == 0) ? p/=2 : q/=2;
10        (p%2 == 0) ? p/=2 : q/=2;
11        (p%3 == 0) ? p/=3 : q/=3;
12        cout << p * q << '\n';
13    }
14    return 0;
15}