# CCPC网络选拔赛 Graph Theory Class

1.若i是质数，i与2相连的边是该质数的邻边中权值最小的，值为2*i
2.若i是和数，则i与自己的因子相连的边权值最小（这里可以找其最小的质因子），值为 i

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;
}
``````