大气宏伟wordpress企业主题,seo课程培训机构,做网站公司不负责任怎么办,加强网站建设工作总结hdu 6889 传说中的人均min25
题意#xff1a;
n个点的完全图#xff0c;边权为lcm(i1,j1)#xff0c;求mst#xff08;最小生成树#xff09;
题解#xff1a;
我一开始以为是推公式#xff0c;毕竟数据范围这么大#xff0c;但是自己画图来看看mst的情况 注意求lc…hdu 6889 传说中的人均min25
题意
n个点的完全图边权为lcm(i1,j1)求mst最小生成树
题解
我一开始以为是推公式毕竟数据范围这么大但是自己画图来看看mst的情况 注意求lcm时每个点都要加一所以后面说点数时默认加一 首先节点2要与所有质数相连因为质数与任何数xx1的lcm都是质数乘xx最小就是2所以所有指数要与2相连那非质数呢非质数就肯定有除1和本身外的因数那就与因数相连lcm也就是其本身其实如果为偶数也可以与2相连毕竟2是所有偶数的因子 最终的结果就是 (n1范围内) ∑(质数-2) * 2∑非质数 ∑非质数 总数和-∑质数 总数和 234…n1 (2n1)n/2(n3)n/2 ∑(质数 2 - 4总数和-∑质数 ∑质数总数和-4 [3,n1]的素数和(34…(n1)) [3,n1]的素数和 (n4) * (n-1)/2
减2是因为节点2不能与自身相连 注意n的范围是1010这玩意咋写 有个神奇的算法叫min25筛详细看知乎本题代码模板也选自知乎 比赛时也出现大量知乎借鉴现象可唯独我就是没做出来难受 通过min25筛就可以在规定时间内算出∑质数这样问题就解决了
代码 #include bits/stdc.h
using namespace std;
typedef long long ll;
const ll N 1000010;typedef long long ll;ll mod;
ll qpow(ll a, ll b)
{ll ans 1;while(b){if(b 1)ans ans * a % mod;a a * a % mod;b / 2;}return ans % mod;
}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%lld, n, mod);ll ans (solve(n 1) - 2 mod) % mod;//质数和 ll inv2 qpow(2, mod - 2) % mod;ll tmp ((n 4) % mod * (n-1) % mod) % mod * inv2 % mod;printf(%lld\n, (ans tmp) % mod);}
}
