題意：給定一個N*N個網格（每條邊上共有N+1個點），從這個網格中取出三個點構成三角形，問一共可以構成多少種三角形。

解法：首先令N' = N+1，那么不考慮直線相交的情況下從N'*N'個點中選出三個點的方案數為C(3, N'*N')；然后考慮到每條平行于水平和垂直線的線段上共有2*N'*C(3, N')種情況需要減去，最后還要減去斜線直線上的情況。

斜線上則只考慮從左上到右下的情況，乘以2表示從右到左是對稱的。對于每一種斜線的情況都可以將左上端點和右下端點固定，然后就可以看作是一個矩形對角線上除去兩個端點外，中間還有多少個點的問題了，對于這個問題，在求凸包上有多少個整數點時應該知道，假設邊為(a, b)，線段上點的個數為gcd(a, b) + 1，除去兩個端點后為gcd(a, b) - 1，因此枚舉出所有的矩形就可以了。

對于邊長為(a, b)的矩形，N*N的矩形中共有(N' - a) * (N' - b)個。因此邊長為(a, b)的情況下，共有(N' - a) * (N' - b) * (gcd(a, b) - 1)中不合法的情況需要減去。但是該題由于N的范圍過大，因此在枚舉邊長是達到了O(N^2)的時間復雜度，肯定會超時的。因此需要優化這個求解的過程：

具體做法是枚舉gcd值，由于gcd值至少為2才會對結果有影響，因此gcd值就可以從2開始枚舉起，且這個gcd值最大為N。若枚舉了gcd值為k，那么有gcd(a, b) = k，則gcd(a/k, b/k) = 1，因此只要知道在某一范圍內互質數的對數，然后再將這些互質的數均乘上一個x即為所求，約定a <= b，由于a、b的取值均為1-N，因此b的取值最大為N / x，那么互質數的對數就是2 * (phi[1] + phi[2] + ... + phi[N / x])，乘以2是因為a，b可以交換位置，后面的求和是因為這么些互質的數均滿足要求。那么對于每一組互質的數m, n，有m = a/k, b = b/k，即a = k*m, b = k*n，因此代入到(N' - a) * (N' - b) * (gcd(a, b) - 1)有(N'*N' - (m + n)*N'*k + m*n*k*k) * (k - 1)。這是對于一組來說，由于枚舉k值，因此k值相同的數對應一起計算，因此可知所有k值相同的數對，N'*N'的系數為前面所討論的總對數，N'*k以及k*k的系數由互質對的成對情況分別能夠求出遞推式。成對是指若gcd(y, N) = 1，那么gcd(N-y, N) = 1 (y < N)。

維護好上面提到的三個系數便可以計算出最后的結果了，計算過程中應防止溢出，代碼如下：

#include <cstdlib> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std;typedef long long LL; const int MaxN = 100000; const int MOD = int(1e9+7); int phi[MaxN+5]; int spair[MaxN+5]; int sadd[MaxN+5]; int smul[MaxN+5];void Euler() {phi[1] = 1;spair[1] = 1, sadd[1] = 2, smul[1] = 1;for (int i = 2; i <= MaxN; ++i) {if (!phi[i]) {for (int j = i; j <= MaxN; j += i) {if (!phi[j]) phi[j] = j;phi[j] -= phi[j] / i;}}// 由于于i互質的數一定是互補的即gcd(x, n) = 1，則gcd(n-x, n) = 1 spair[i] = (1LL * spair[i-1] + phi[i] * 2) % MOD;sadd[i] = (1LL * sadd[i-1] + 1LL * phi[i] * 3 % MOD * i) % MOD;smul[i] = (1LL * smul[i-1] + 1LL * phi[i] * i % MOD * i) % MOD;} }LL cal(LL x[]) {// 因為有除法，因此要將除數先進行處理for (int i = 0; i < 3; ++i) {if (x[i] % 2 == 0) {x[i] /= 2;break;}}for (int i = 0; i < 3; ++i) {if (x[i] % 3 == 0) {x[i] /= 3;break;}}for (int i = 0; i < 3; ++i) x[i] %= MOD;return x[0]%MOD*x[1]%MOD*x[2]%MOD; }int main() {Euler();int T, N;scanf("%d", &T);while (T--) {LL ret, exp = 0;scanf("%d", &N); // 坐標的取值范圍[0,N]，共有N+1種選擇 ++N;LL a[3] = {1LL*N*N, 1LL*N*N-1, 1LL*N*N-2};LL b[3] = {N, N-1, N-2};ret = cal(a);ret = ((ret - cal(b)*2%MOD*N%MOD) % MOD + MOD) % MOD;// 也可將mod乘以6，先做乘法然后mod這個新的數，相當于把余數擴大了6倍，然后再除以6 for (int k = 2; k < N; ++k) {int t = (N-1) / k;exp = (exp + 1LL*(k-1)*(1LL*spair[t]*N%MOD*N%MOD))%MOD;exp = ((exp - 1LL*(k-1)*(1LL*sadd[t]*k%MOD*N%MOD)%MOD)%MOD + MOD) % MOD;exp = (exp + 1LL*(k-1)*k%MOD*k%MOD*smul[t]%MOD)%MOD;}ret = ((ret-2*exp)%MOD+MOD)%MOD;printf("%I64d\n", ret);}return 0; }

?

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的HDU-4483 Lattice triangle 数论的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。