HDU-4483 Lattice triangle 数论
題意:給定一個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 数论的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: Android消息处理系统——Loope
- 下一篇: Javascript 两种 functi