宁波制作网站的公司,郑州 网站建设:,怎么做购物优惠券网站,桂林临桂区建设局网站Minimum spanning tree HDU - 6954
题意#xff1a;
给定n-1个点#xff0c;编号从2到n#xff0c;两点a和b之间的边权重为lcm#xff08;a#xff0c;b#xff09;。请找出它们形成的最小生成树。 2n10000000
题解#xff1a;
这题一看就眼熟。。。这不是去…Minimum spanning tree HDU - 6954
题意
给定n-1个点编号从2到n两点a和b之间的边权重为lcmab。请找出它们形成的最小生成树。 2n10000000
题解
这题一看就眼熟。。。这不是去年的CCPC网络赛吗当时就差这个题进区域赛CCPC里面数据范围是n10 ^10 , 这个是10 ^7,前者用min25筛做后者直接用欧拉筛就可以 HDU 6889 Graph Theory Class(CCPC网络赛)
代码
min25筛做法 min25筛模板出处
#include bits/stdc.h
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) );}
}欧拉筛做法
