生活随笔
收集整理的這篇文章主要介紹了
Minimum spanning tree HDU - 6954
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
Minimum spanning tree HDU - 6954
題意：
給定n-1個點，編號從2到n，兩點a和b之間的邊權重為lcm（a，b）。請找出它們形成的最小生成樹。
2<=n<=10000000
題解：
這題一看就眼熟。。。這不是去年的CCPC網絡賽嗎，當時就差這個題進區域賽，CCPC里面數據范圍是n<=10 ^10 , 這個是10 ^7,前者用min25篩做，后者直接用歐拉篩就可以
HDU 6889 Graph Theory Class(CCPC網絡賽)
代碼：
min25篩做法
min25篩模板出處
using namespace std
;
typedef long long ll
;
const ll N
= 1000010
;typedef long long ll
;ll qpow
(ll a, ll b
)
{ll ans
= 1
;while
(b
){if
(b
& 1
)ans
= ans * a
;a
= a * a
;b /
= 2
;}return ans
;
}ll prime
[N
], id1
[N
], id2
[N
], flag
[N
], ncnt, m
;ll g
[N
], sum
[N
], a
[N
], T, n
;inline ll ID
(ll x
)
{return x
<= T ? id1
[x
] : id2
[n / x
];
}inline ll calc
(ll x
)
{return x *
(x + 1
) / 2 - 1
;
}inline ll f
(ll x
)
{return x
;
}inline void init
()
{ncnt
= m
= 0
;T
= sqrt
(n + 0.5
);for (ll i
= 2
; i
<= T
; i++
){if (!flag
[i
])prime
[++ncnt
] = i, sum
[ncnt
] = sum
[ncnt - 1
] + i
;for (ll j
= 1
; j
<= ncnt
&& i * prime
[j
] <= T
; j++
){flag
[i * prime
[j
]] = 1
;if (i % prime
[j
] == 0
)break;}}for (ll l
= 1
; l
<= n
; l
= n /
(n / l
) + 1
){a
[++m
] = n / l
;if (a
[m
] <= T
)id1
[a
[m
]] = m
;elseid2
[n / a
[m
]] = m
;g
[m
] = calc
(a
[m
]);}for (ll i
= 1
; i
<= ncnt
; i++
)for (ll j
= 1
; j
<= m
&& (ll
)prime
[i
] * prime
[i
] <= a
[j
]; j++
)g
[j
] = g
[j
] -
(ll
)prime
[i
] *
(g
[ID
(a
[j
] / prime
[i
])] - sum
[i - 1
]);
}inline ll solve
(ll x
)
{if (x
<= 1
)return x
;return n
= x, init
(), g
[ID
(n
)];
}int main
()
{ll n, t
;scanf
("%lld",
&t
);while
(t--
) {scanf
("%lld",
&n
);n--
;ll ans
= (solve
(n + 1
) - 2
);//質數和 ll tmp
= ((n + 4
) *
(n-1
) ) /2
;printf
("%lld\n",
(ans + tmp
) );}
}
歐拉篩做法：
總結
以上是生活随笔為你收集整理的Minimum spanning tree HDU - 6954的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
