分析:一道比較讓人頭疼的數(shù)學(xué)題.

? ? ?先考慮怎么讓分出來(lái)的三角形相似，先不考慮每個(gè)三角形的具體邊長(zhǎng)，設(shè)每個(gè)三角形的周長(zhǎng)為li,則可知必然有一個(gè)數(shù)g = gcd{li},每一個(gè)三角形的周長(zhǎng)都是g的倍數(shù)，這樣就會(huì)有n/g個(gè)單位三角形,我們只需要把n/g分配給若干個(gè)三角形就可以了，利用隔板法，可以算出方案數(shù)為2^(n/g - 1).

? ? ?再來(lái)考慮知道了周長(zhǎng)怎么求這個(gè)周長(zhǎng)的三角形有多少個(gè).為了方便起見(jiàn)，設(shè)a ≤ b ≤ c,s = a + b + c,如果b = c,那么s = a + 2b,b的取值范圍就是[g/3上取整,(g-1)/2下取整],看看取值范圍內(nèi)有多少個(gè)整數(shù)就有多少種方案.如果b < c,那么可以把c--,直到變成b=c,那么就是f[i] = f[i - 1],但是這樣有一種特殊情況：a + b = c,這在f[i - 1]中是合法的,但是我們?cè)谔幚淼臅r(shí)候要減掉這種方案.s = 2c,c = g/2,顯然只有g(shù)是偶數(shù)的時(shí)候才會(huì)出現(xiàn)這種情況，這時(shí)a和b只能取g/4個(gè)數(shù)，方案數(shù)減去g/4就可以了.

? ? ?但是這樣還是不行，如果一個(gè)三角形邊長(zhǎng)是2,2,3,另外一個(gè)是4,4,6,那么可以將前面一個(gè)三角形作為單位三角形分配給后面的三角形,直接計(jì)算會(huì)將一個(gè)方案算多次，所以我們要求的f[s]，s = a + b + c中的a,b,c必須是互質(zhì)的，為了去重，每一個(gè)f[s] -= f[k],k | s.就可以了.

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath>using namespace std;const int mod = 1e9 + 7;typedef long long ll; ll n, f[1000010], p[1000010], cnt, mi[1000010], ans;void add(ll &a, ll b) {a += b;if (a >= mod)a -= mod; }int main() {scanf("%lld", &n);for (ll i = 3; i <= n; i++){f[i] = f[i - 1];add(f[i], (i - 1) / 2 - ceil((double)i * 1.0 / 3) + 1);if (!(i & 1))f[i] -= i / 4;}for (ll i = 1; i * i <= n; i++)if (n % i == 0){if (i * i != n){p[++cnt] = i;p[++cnt] = n / i;}elsep[++cnt] = i;}sort(p + 1, p + 1 + cnt);for (ll i = 1; i <= cnt; i++)for (ll j = 1; j < i; j++)if (p[i] % p[j] == 0)add(f[p[i]], mod - f[p[j]]);mi[0] = 1;for (ll i = 1; i <= n; i++){mi[i] = mi[i - 1];add(mi[i], mi[i - 1]);}for (ll i = 1; i <= cnt; i++)add(ans, mi[n / p[i] - 1] * f[p[i]] % mod);printf("%lld\n", ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zbtrs/p/7650595.html

總結(jié)

以上是生活随笔為你收集整理的清北学堂模拟赛d3t2 b的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。