2019 百度之星初赛三 补题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int mod=998244353;
const int N=1e3+10; 
const int M=2e3+10;
int t,n,m,u,v,w;
int head[N],ans[N],cnt;
bool vis[N];
ll dis[N],res; 
struct edge{int to,nex;ll w;}e[M*2];
struct node
{
  ll w;
  int v;
  node(ll a,int c):w(a),v(c){
  } 
};
bool operator>(node a,node b)
{
	return a.w>b.w;
}
priority_queue<node,vector<node>,greater<node> >q;
void init()
{
	cnt=0;
	memset(head,0,sizeof head);
}
void add(int u,int v,ll w)
{
	e[++cnt].to=v;
	e[cnt].w=w;
	e[cnt].nex=head[u];
	head[u]=cnt;
}
void dijkstra(int s)
{
	memset(vis,0,sizeof vis);
	memset(ans,0,sizeof ans);
	for(int i=1;i<=n;++i)
	dis[i]=1e18;
	q.push(node(0,s));//说明从哪条边转移到这点的 
	dis[s]=0;
	while(!q.empty())
	{
		node tmp=q.top();
		q.pop();
		int v=tmp.v;
		if(vis[v])continue;
		vis[v]=1;
		for(int i=head[v];i;i=e[i].nex)
		{
			int to=e[i].to;
			ll w=e[i].w;
			if(dis[to]>dis[v]+w)
			{
				dis[to]=dis[v]+w;
				if(v!=s)ans[to]=max(ans[v],v);
				q.push(node(dis[to],to));
			}
			else if(dis[to]==dis[v]+w)
			{
				if(v!=s)ans[to]=min(ans[to],max(ans[v],v)); 
			}
		}
	}
} 
int main()
{ 
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		init();
		res=0;
		while(m--)
		{
			scanf("%d%d%d",&u,&v,&w);
			add(u,v,w);add(v,u,w);
		}
		for(int i=1;i<=n;++i)
		{
			dijkstra(i);
			for(int j=1;j<=n;++j)
			res+=ans[j];
		}
		printf("%lldn",res%mod);
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
bool ok[maxn];
int prime[maxn],mu[maxn],cnt;
int T,n,m,mn;
ll sum[maxn],ans,ans1,ans2,ans3;
void sieve()
{
	mu[1]=1;
	for(ll i=2;i<maxn;++i)
	{
		if(!ok[i])
		{
			prime[cnt++]=i;
			mu[i]=-1;
		}
		for(int j=0;j<cnt;++j)
		{
			if(i*prime[j]>=maxn)break;
			ok[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				mu[i*prime[j]]=0;//如果开的是全局,就不用管 
				break; 
			}
			else mu[i*prime[j]]=-mu[i];
		}
	}
	for(int i=1;i<maxn;++i)//d
	{
		for(int j=i;j<maxn;j+=i)//d*k
		sum[j]+=mu[i]*mu[j/i];
	}	
}
int main()
{
	sieve();
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		mn=min(n,m);
		ans=0;
		for(int i=1;i<=mn;++i)
		{
			ans1=sum[i];
			ans2=0;
			for(int j=i;j<=n;j+=i)
			ans2+=mu[j];
			ans3=0;
			for(int j=i;j<=m;j+=i)
			ans3+=mu[j];
			ans+=ans1*ans2*ans3;
		}
		printf("%lldn",ans);
	} 
	return 0;
}