CCPC网络选拔赛 Graph Theory Class

题目大意:

要求一颗最小生成树,其中图的结点标号从1-n,任意两个结点(i,j)间的边权值为lcm(i+1,j+1)

题意分析:

其实可以直接看成编号为从2到n+1,边的权值就是lcm(i,j)
然后容易想到,对于i
1.若i是质数,i与2相连的边是该质数的邻边中权值最小的,值为2*i
2.若i是和数,则i与自己的因子相连的边权值最小(这里可以找其最小的质因子),值为 i

所以对于质数与2相连的边合数与其因子相连的边,这样得到的生成树为最小生成树。
再说说这样取为什么能构成树,可以将结点按序号升序排列,然后从前往后连接各个顶点,可以发现这样的连接方法与prim算法相同(从一个结点开始,每次连接一个新的结点),所以得到的是一棵树。
然后你就会发现,生成树的权值中,合数加了1次,质数加了两次。所以结果可以分解为3-n+1的所有数的和加上3-n+1的所有质数的和。


注意:这道题数据范围较大,所以要用到求质数和的模板。以及除法取模时要求逆元

AC代码:
#includeiostream
#includecmath
#includecstdio
using namespace std;
typedef long long ll;
const int MAX_N=55;
int arr[MAX_N][MAX_N];
inline ll FUN(ll v,ll N,ll nd,ll nv){return v=nd?(N/v-1):(nv-v);}

ll PrimeSum(ll N) 
{
    ll *S,*V,r=(ll)sqrt(N);
	ll nd=N/r;
	ll nv=r+nd-1;
	V=new ll[nv],S=new ll[nv];
    for (ll i=0;ir;i++) V[i]=N/(i+1);
    for (ll i=r;inv;i++) V[i]=V[i-1]-1;
    for (ll i=0; inv; i++) S[i]=V[i]*(V[i]+1)/2-1;
    for (ll p=2; p=r; p++) 
	{
        if (S[nv-p]  S[nv-p+1]) 
		{
            ll sp = S[nv-p+1];
            ll p2 = p*p;
            for(ll i=0;inv;i++) 
			{
                if(V[i]=p2) S[i]-=p*(S[FUN(V[i]/p,N,nd,nv)]-sp);
				else break;
            }
        }
    }
    return S[0];
}
ll Pow(ll  a,ll b,ll MOD)
{
	ll ans=1;
	a%=MOD;
	while(b0)
	{
		if(b1)ans=(ans*a)%MOD;
		a=(a*a)%MOD;
		b=1; 
	}
	return ans%MOD;											
}

int main()
{
	int t;
	cint;
	while(t--)
	{
		ll n,k;
		cinnk;
		if(n==1)
		{
			cout0'\n';
			continue;
		}
		if(n==2)
		{
			cout6%k'\n';
			continue;
		}
		ll sum=0;
		sum+=PrimeSum(n+1)-2;
		sum %=k;
		sum+=((3+n+1)%k*(n-1))%k*Pow(2,k-2,k)%k;
		coutsum%k'\n';
	}
	return 0;
}
最新回复(0)
/jishuxzK1ADRCBY8kaui4ZJu47T0Uv9o1JJKdA4tMIrNqKqE_3D4794740
8 简首页