devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

2023第十四届蓝桥杯 C/C++大学生A组省赛 满分题解_蓝桥杯2023真题解析c/c++大学a组

作者：IT小白 | 2024-04-11 16:27:50

赞

踩

蓝桥杯2023真题解析c/c++大学a组

写在前面

以下代码，目前均可通过民间OJ数据（dotcpp & New Online Judge），

两个OJ题目互补，能构成全集，可以到对应链接下搜题提交（感谢OJ对题目的支持）

如果发现任何问题，包含但不限于算法思路出错、OJ数据弱算法实际超时、存在没考虑到的边界情况等，请及时联系作者

e6776398414e412199c43c9775dc086d.png​

dadf3bb6f9044639ab96157a3dceeb25.png​

更新（2023年5月14日）

洛谷更新了蓝桥杯2023年的题目，A组题号P9230-P9238

于是，把题目又都交了一遍，倒数第二题像素放置直接爆搜超时，

60个点TLE了8个点，加了个bitset记忆化就过了，代码已更新

题解

A.幸运数（模拟）

题面

caec59f883fa4483947d5498fb767ae7.png​

题解 

由于是填空题，按题意本地暴力，几秒就跑出来结果了，直接交结果

代码

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int ans;
  4. int main(){
  5. 	/*
  6. 	for(int i=1;i<=100000000;++i){
  7. 		int cnt=0;
  8. 		for(int j=i;j;j/=10)cnt++;
  9. 		if(cnt&1)continue;
  10. 		int sum=0,now=0;
  11. 		for(int j=i;j;j/=10){
  12. 			now++;
  13. 			if(now<=cnt/2)sum+=j%10;
  14. 			else sum-=j%10;
  15. 		}
  16. 		if(!sum)ans++;
  17. 	}
  18. 	printf("%d\n",ans);
  19. 	*/
  20. 	puts("4430091");
  21. 	return 0;
  22. }

B.有奖问答（搜索/dp）

题面

e7a9ee7d17b74f6085a71303a327bbe6.png​

题解

1. 搜索：2的30次方种可能，每次要么+10要么清零，遇到100分时，直接return，几秒跑出来结果后，直接交结果

2. dp：dp[i][j]表示前i轮过后分数为j的方案数，注意中间可以随时停止

代码（dp）

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll dp[31][101],ans;
  5. int main(){
  6. 	dp[0][0]=1;
  7. 	for(int i=0;i<30;++i){
  8. 		for(int j=0;j<100;j+=10){
  9. 			if(!dp[i][j])continue;
  10. 			if(j<90)dp[i+1][j+10]+=dp[i][j];
  11. 			dp[i+1][0]+=dp[i][j];
  12. 		}
  13. 		ans+=dp[i+1][70];
  14. 	}
  15. 	printf("%lld\n",ans);
  16. 	//puts("8335366");
  17. 	return 0;
  18. }

C.平方差（构造/规律）

题面

8eb8e16f67214fae927127238dd5bec6.png​

题解

打表或构造发现，形如4k+2的数无法被表示，

统计[l,r]的答案，前缀和作差，转化为[1,r]的答案减去[1,l-1]的答案

而[1,x]中，形如4k+2的数的个数为(x+2)/4

证明的话，x=(y+z)(y-z)，注意到y+z和y-z同奇偶，

1. y+z为奇数时，x为奇数；y+z为偶数时，x为4的倍数，这表明4k+2无法被取到

2. gif.latex?2k&plus;1%3D%28k&plus;1%29%5E2-k%5E2​，gif.latex?4k%3D%28k&plus;1%29%5E2-%28k-1%29%5E2​，这表明奇数和4的倍数均能被取到

代码

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N=500;
  5. bool vis[N];
  6. int l,r;
  7. int cal(int x){
  8. 	return x-(x+2)/4;
  9. }
  10. int main(){
  11. 	/*
  12. 	for(int i=0;i<=50;++i){
  13. 		for(int j=0;j<=i;++j){
  14. 			int v=i*i-j*j;
  15. 			if(v>=0 && v<N)vis[v]=1;
  16. 		}
  17. 	}
  18. 	for(int i=0;i<=100;++i){
  19. 		if(!vis[i])printf("i:%d\n",i);
  20. 	}*/
  21. 	scanf("%d%d",&l,&r);
  22. 	printf("%d\n",cal(r)-cal(l-1));
  23. 	return 0;
  24. }
  25. //x=(y+z)(y-z)
  26. //2k+1=(k+1)^2-k^2
  27. //4k=(k+1)^2-(k-1)^2

D.更小的数（区间dp）

题面

82a9c62506d54fd59e6605db7e56ce5e.png​

935de08a9a484ee0ac5f8e72dffbeaf0.png​

题解

未反转的段仍相同不用关注，只需关注反转的段，

记反转前的串为old（即num串），之后的串为new

运用递归/记忆化搜索的思想，有以下几种情况

1. 当i=j时，new[i,j]不小于old[i,j]

2. 当i+1=j时，new[i,j]小于old[i,j]，当且仅当new[i]<old[i]，即num[j]<num[i]

3. 否则，

①若num[j]<num[i]，new[i,j]一定小于old[i,j]

②若num[j]=num[i]，则可以去掉这两个字母，只需比较new[i+1,j-1]和old[i+1,j-1]

③若num[j]>num[i]，new[i,j]一定大于old[i,j]

从短串递推到长串，就是区间dp了，当然直接写记忆化搜索也行

代码中，dp[i][j]=1表示反转后更小，=0表示反转后大于等于原来

代码

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N=5e3+10;
  5. int n,dp[N][N],ans;
  6. char s[N];
  7. int main(){
  8. 	scanf("%s",s);
  9. 	n=strlen(s);
  10. 	for(int len=2;len<=n;++len){
  11. 		for(int l=0;l+len-1<n;++l){
  12. 			int r=l+len-1;
  13. 			if(s[l]>s[r])dp[l][r]=1;
  14. 			else if(s[l]==s[r])dp[l][r]=dp[l+1][r-1];
  15. 			ans+=(dp[l][r]==1);
  16. 		}
  17. 	}
  18. 	printf("%d\n",ans);
  19. 	return 0;
  20. }
  21. //4321
  22. //1234

E.更小的数（树上莫队/启发式合并）

题面

20ff774db5ec439d8ebe4d0e773159f5.png​

题解

1. 树上莫队：

树上莫队=莫队+dfs序

建树后求dfs序，每个子树对应的dfs区间就是一个询问区间，将询问区间排序后套用莫队，

维护当前颜色i出现的次数now[i]、出现次数为i的颜色种类数freq[i]

任取区间内出现的一种颜色x，若now[x]*freq[now[x]]=区间长度则合法，否则不合法

复杂度O(nsqrt(n))

2. 启发式合并：

可以维护相同的东西，只是套了个启发式合并的壳

重儿子直接继承当前维护的信息，把轻儿子维护的信息往重儿子上合并，

由于每个点至多出现在log个轻儿子所在的子树里，复杂度O(nlogn)

代码（树上莫队）

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N=2e5+10;
  5. int n,m,c[N],f,in[N],out[N],tot,id[N],pos[N],sz;
  6. int now[N],freq[N],ans;
  7. map<int,int>vis;
  8. vector<int>e[N];
  9. struct node{
  10. 	int l,r;
  11. }q[N];
  12. void add(int col,int v){
  13. 	freq[now[col]]--;
  14. 	now[col]+=v;
  15. 	freq[now[col]]++;
  16. }
  17. bool operator<(node a,node b){
  18. 	if(pos[a.l]==pos[b.l]){
  19. 		if(pos[a.l]&1)return a.r>b.r;
  20. 		else return a.r<b.r;
  21. 	}
  22. 	return a.l<b.l;
  23. }
  24. void dfs(int u){
  25. 	in[u]=++tot;
  26. 	id[tot]=u;
  27. 	for(auto &v:e[u]){
  28. 		dfs(v);
  29. 	}
  30. 	out[u]=tot;
  31. 	q[++m]={in[u],out[u]};
  32. }
  33. int main(){
  34. 	scanf("%d",&n);
  35. 	for(int i=1;i<=n;++i){
  36. 		scanf("%d%d",&c[i],&f);
  37. 		if(!vis.count(c[i])){
  38. 			vis[c[i]]=1;
  39. 			freq[0]++;
  40. 		}
  41. 		if(i>1)e[f].push_back(i);
  42. 	}
  43. 	dfs(1);
  44. 	sz=(int)sqrt(n);
  45. 	for(int i=1;i<=n;++i){
  46. 		pos[i]=1+(i-1)/sz;
  47. 	}
  48. 	sort(q+1,q+n+1);
  49. 	int l=1,r=1;
  50. 	add(c[1],1);
  51. 	for(int i=1;i<=n;++i){
  52. 		for(;r<q[i].r;r++)add(c[id[r+1]],1);
  53. 		for(;r>q[i].r;r--)add(c[id[r]],-1);
  54. 		for(;l<q[i].l;l++)add(c[id[l]],-1);
  55. 		for(;l>q[i].l;l--)add(c[id[l-1]],1);
  56. 		int col=c[id[l]],cnt=now[col],f=freq[cnt];
  57. 		if(f*cnt==r-l+1)ans++;
  58. 	}
  59. 	printf("%d\n",ans);
  60. 	return 0;
  61. }
  62. /*
  63. 6
  64. 2 0
  65. 2 1
  66. 1 2
  67. 3 3
  68. 3 4
  69. 1 4
  70. */

F.买瓜（折半枚举+三进制枚举/枚举子集的子集）

题面

b43382620fe148e89ff81f9ce5eede22.png​

题解

每个西瓜三种选择：不选，选但不劈，选且劈两半

直接三进制枚举的话，3的30次方，复杂度爆炸

考虑拆成两半枚举（折半枚举，也叫meet-in-middle）

分别维护3的15次方大小的集合a、b，

答案只可能完全来自a、或者完全来自b、或者ab各一部分

ab各一部分的话，在枚举b集合内的元素对应的和为x时，到a集合内查元素和m-x是否存在

复杂度O(3^15*log(3^15))​，大概3e8多，时间1s(题面pdf)，比较极限，难以通过(New Online Judge2s dotcpp3s)，试了试unordered_map去卡2s也TLE了，而瓶颈主要在集合查的这个log，

所以手写哈希（开散列），将log这个常数再压一压，就可以通过2s的题了

256M空间其实也比较极限，哈希模数那个数组不要开太大（调小了TLE调大了MLE）

代码

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<int,int> P;
  5. #define fi first
  6. #define se second
  7. const int N=32,M=1<<15,mod=19260817,S=14348907;
  8. int n,bit[M];
  9. int head[mod],nex[S],cnt;
  10. P b[S];
  11. ll m,a[N],f[M],g[M],sum;
  12. inline void upd(int x,int v){
  13.     int u=x%mod;
  14.     for(int i=head[u];i;i=nex[i]){
  15.         if(b[i].fi==x){
  16.             b[i].se=min(b[i].se,v);
  17.             return;
  18.         }
  19.     }
  20.     b[++cnt]=P(x,v);
  21.     nex[cnt]=head[u];
  22.     head[u]=cnt;
  23. }
  24. inline int cal(int x){
  25.     int u=x%mod;
  26.     for(int i=head[u];i;i=nex[i]){
  27.         if(b[i].fi==x)return b[i].se;
  28.     }
  29.     return N;
  30. }
  31. int sol(){
  32.     if(sum==m)return 0;
  33.     if(n==1){
  34.         if(a[0]/2==m)return 1;
  35.         return -1;
  36.     }
  37.     int ans=N;
  38.     for(int i=1;i<M;++i){
  39.         bit[i]=bit[i>>1]+(i&1);
  40.     }
  41.     int l=n/2,lb=1<<l,r=n-n/2,rb=1<<r;
  42.     for(int i=0;i<l;++i){
  43.         f[1<<i]=a[i];
  44.     }
  45.     for(int i=1;i<lb;++i){
  46.         int x=i&-i;
  47.         f[i]=f[x]+f[i^x];
  48.         if((f[i]>>1)>m)continue;
  49.         for(int j=i;;j=(j-1)&i){
  50.             ll v=(f[j]>>1)+f[j^i];
  51.             if(v<=m){
  52.                 if(v==m)ans=min(ans,bit[j]);
  53.                 else upd((int)v,bit[j]);
  54.             }
  55.             if(!j)break;
  56.         }
  57.     }
  58.     for(int i=0;i<r;++i){
  59.         g[1<<i]=a[l+i];
  60.     }
  61.     for(int i=1;i<rb;++i){
  62.         int x=i&-i;
  63.         g[i]=g[x]+g[i^x];
  64.         if((g[i]>>1)>m)continue;
  65.         for(int j=i;;j=(j-1)&i){
  66.             ll v=(g[j]>>1)+g[j^i];
  67.             if(v<=m){
  68.                 if(v==m)ans=min(ans,bit[j]);
  69.                 else ans=min(ans,cal((int)(m-v))+bit[j]);
  70.             }
  71.             if(!j)break;
  72.         }
  73.     }
  74.     if(ans>n)ans=-1;
  75.     return ans;
  76. }
  77. int main(){
  78.     scanf("%d%lld",&n,&m);
  79.     m*=2;
  80.     for(int i=0;i<n;++i){
  81.         scanf("%lld",&a[i]);
  82.         a[i]*=2;
  83.         sum+=a[i];
  84.     }
  85.     printf("%d\n",sol());
  86.     return 0;
  87. }

G.网络稳定性（kruskal重构树）

题目dc0d1cab46c6465796ae40cd3ffce60f.png​

d994cfa3c38b4e6d97835bb138b3ab7f.png​

题解

kruskal重构树裸题，

重构树听上去高端，实则就是在kruskal建最大生成树的过程中额外建点、赋权

比如，u和v当前不在一个集合里，通过w这条边合并时，

新开一个点x，令x是u和v的父亲，而x的权值为w，

查询时，查u和v的lca的权值即可，即为最大连通路径上的最小连通权值

因为按权值从大到小遍历，已经通过权值大的边，使得点之间尽可能连通了

代码

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N=4e5+10,M=3e5+10,K=20;
  5. int n,m,q,u,v,par[N],a[N],f[N][K],dep[N];
  6. bool vis[N];
  7. vector<int>E[N];
  8. struct edge{
  9. 	int u,v,w;
  10. }e[M];
  11. int find(int x){
  12. 	return par[x]==x?x:par[x]=find(par[x]);
  13. }
  14. bool cmp(edge a,edge b){
  15. 	return a.w>b.w;
  16. }
  17. void dfs(int u,int fa){
  18. 	vis[u]=1;
  19. 	f[u][0]=fa;
  20. 	dep[u]=dep[fa]+1;
  21. 	for(auto &v:E[u]){
  22. 		if(v==fa)continue;
  23. 		dfs(v,u);
  24. 	}
  25. }
  26. int lca(int u,int v){
  27. 	if(dep[u]<dep[v])swap(u,v);
  28. 	int d=dep[u]-dep[v];
  29. 	for(int i=K-1;i>=0;--i){
  30. 		if(d>>i&1)u=f[u][i];
  31. 	}
  32. 	if(u==v)return u;
  33. 	for(int i=K-1;i>=0;--i){
  34. 		if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
  35. 	}
  36. 	return f[u][0];
  37. }
  38. int main(){
  39. 	scanf("%d%d%d",&n,&m,&q);
  40. 	for(int i=1;i<=n+m;++i){
  41. 		par[i]=i;
  42. 	}
  43. 	for(int i=1;i<=m;++i){
  44. 		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
  45. 	}
  46. 	sort(e+1,e+m+1,cmp);
  47. 	int cur=n;
  48. 	for(int i=1;i<=m;++i){
  49. 		int u=e[i].u,v=e[i].v,w=e[i].w;
  50. 		u=find(u),v=find(v);
  51. 		if(u==v)continue;
  52. 		++cur;
  53. 		par[u]=par[v]=cur;
  54. 		E[cur].push_back(u);
  55. 		E[cur].push_back(v);
  56. 		a[cur]=w;
  57. 	}
  58. 	for(int i=cur;i>=1;--i){
  59. 		if(!vis[i])dfs(i,0);
  60. 	}
  61. 	for(int j=1;j<K;++j){
  62. 		for(int i=1;i<=cur;++i){
  63. 			f[i][j]=f[f[i][j-1]][j-1];
  64. 		}
  65. 	}
  66. 	while(q--){
  67. 		scanf("%d%d",&u,&v);
  68. 		if(find(u)!=find(v)){
  69. 			puts("-1");
  70. 			continue;
  71. 		}
  72. 		printf("%d\n",a[lca(u,v)]);
  73. 	}
  74. 	return 0;
  75. }
  76. /*
  77. 5 4 3 
  78. 1 2 5
  79. 2 3 6
  80. 3 4 1
  81. 1 4 3
  82. 1 5
  83. 2 4
  84. 1 3
  85. */

H. 异或和之和（按位计算贡献）

题目

0e5f81b03a4349249b083a99395f19c8.png​

题解

按每个二进制位i考虑，从而转化为0、1序列的问题

一个子段[l,r]在第i位有贡献，当且仅当[l,r]内第i位出现的次数为奇数次，

前缀和做差[l,r]=[1,r]减[1,l-1]，所以维护当前有多少个前缀是奇数，有多少个前缀是偶数

[l,r]为奇数，若[1,r]为偶数则要求[1,l-1]为奇数，反之同理，

枚举每个右端点，统计与其对应的有贡献的左端点，计算答案

代码

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N=1e5+10;
  5. int n,a[N],sum[2];
  6. ll ans;
  7. int main(){
  8. 	scanf("%d",&n);
  9. 	for(int i=1;i<=n;++i){
  10. 		scanf("%d",&a[i]);
  11. 	}
  12. 	for(int i=0;i<=20;++i){
  13. 		sum[0]=1,sum[1]=0;
  14. 		int now=0;
  15. 		ll all=0;
  16. 		for(int j=1;j<=n;++j){
  17. 			int v=a[j]>>i&1;
  18. 			now^=v;
  19. 			all+=sum[now^1];
  20. 			sum[now]++;
  21. 		}
  22. 		ans+=all*(1ll<<i);
  23. 	}
  24. 	printf("%lld\n",ans);
  25. 	return 0;
  26. }
  27. /*
  28. 5
  29. 1 2 3 4 5
  30. */

I. 像素放置（搜索）

题面

8f6b927be6c2417a9c707e98262a9510.png​

题解

写状压的话感觉总难免需要关注三行的有效状态，

复杂度好像更没有办法保证，所以写了搜索剪枝，

总体思路还是枚举每一位填0还是填1，加入了校验机制，以及搜到解之后直接return

搜索剪枝也要用到插头dp（轮廓线dp）的思想，配合记忆化

洛谷的数据足够强，没加记忆化没过

直接的想法是dp[10][10][1<<22]

dp[i][j][k]表示当前搜到了(i,j)这个格子，而前面2m+2个格子的状态是k时，这个状态是否搜到过

由于搜到解后就返回答案，这么记录，只是为了避免重复搜无效的状态

由于直接int数组开不下，所以用bitset将空间压为1/32，bitset<M>dp[10][10]

 如左图，当(i,j)位于行初时，只需关注前2*m个格子；再往右一格时，只需关注前2*m+1个格子，

再往右两格及更右时，只需关注前2*m+2个格子，直至行尾，最多只需关注22个格子

对于行越界的情形，不妨认为上面有两行全0的空行

复杂度O(n*m*2^{2*m+2})

a[i][j]：原图转化过来的数字，下划线转成了INF

b[i][j]：当前填的答案数组

cur[i][j]：(i,j)本身及(i,j)周围一圈合法位置中，当前填了几个1

填一个数时，考虑它本身及周围一圈的合法位置（最多9个）

校验机制是：

1. 如果当前填了这个数，导致超过上限，即cur[i][j]>a[i][j]，则不合法

2. 如果当前填的格子，是格子(i,j)管辖的最后一个格子，填完这个数后，a[i][j]和cur[i][j]不等，则也不合法

代码

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int S=15,N=10,M=1<<22,INF=0x3f3f3f3f;
  4. int n,m,a[S][S],b[S][S],cur[S][S];
  5. bitset<M>dp[N][N];
  6. char s[S][S];
  7. bool ok;
  8. bool in(int x,int y){
  9. 	return 0<=x && x<n && 0<=y && y<m && a[x][y]!=INF;
  10. }
  11. bool can(int x,int y,int v){
  12. 	for(int i=-1;i<=1;++i){
  13. 		for(int j=-1;j<=1;++j){
  14. 			int nx=x+i,ny=y+j;
  15. 			if(in(nx,ny) && cur[nx][ny]+v>a[nx][ny])return 0;
  16. 		}
  17. 	}
  18. 	if(in(x-1,y-1) && cur[x-1][y-1]+v<a[x-1][y-1])return 0;
  19. 	if(x==n-1 && in(x,y-1) && cur[x][y-1]+v<a[x][y-1])return 0;
  20. 	if(y==m-1 && in(x-1,y) && cur[x-1][y]+v<a[x-1][y])return 0;
  21. 	return 1;
  22. }
  23. void dfs(int x,int y,int w){
  24. 	//cnt++;
  25. 	if(x==n && y==0){
  26. 		ok=1;
  27. 		for(int i=0;i<n;++i){
  28. 			for(int j=0;j<m;++j){
  29. 				printf("%d",b[i][j]);
  30. 			}
  31. 			puts("");
  32. 		}
  33. 		return;
  34. 	}
  35. 	if(ok)return;
  36. 	if(dp[x][y][w])return;
  37. 	dp[x][y][w]=1;
  38. 	for(int v=0;v<=1;++v){
  39. 		if(ok)return;
  40. 		if(can(x,y,v)){
  41. 			b[x][y]=v;
  42. 			if(v){
  43. 				for(int i=-1;i<=1;++i){
  44. 					for(int j=-1;j<=1;++j){
  45. 						int nx=x+i,ny=y+j;
  46. 						if(!in(nx,ny))continue;
  47. 						cur[nx][ny]++;
  48. 					}
  49. 				}
  50. 			}
  51. 			int nw=(w<<1)|v;
  52. 			if(y==m-1)dfs(x+1,0,nw&((1<<(2*m))-1));
  53. 			else dfs(x,y+1,nw&((1<<(2*m+2))-1));
  54. 			if(v){
  55. 				for(int i=-1;i<=1;++i){
  56. 					for(int j=-1;j<=1;++j){
  57. 						int nx=x+i,ny=y+j;
  58. 						if(!in(nx,ny))continue;
  59. 						cur[nx][ny]--;
  60. 					}
  61. 				}
  62. 			}
  63. 		}
  64. 	}
  65. }
  66. int main(){
  67. 	scanf("%d%d",&n,&m);
  68. 	for(int i=0;i<n;++i){
  69. 		scanf("%s",s[i]);
  70. 		for(int j=0;j<m;++j){
  71. 			a[i][j]=INF;
  72. 			if(s[i][j]!='_')a[i][j]=s[i][j]-'0';
  73. 		}
  74. 	}
  75. 	dfs(0,0,0);
  76. 	//printf("cnt:%d\n",cnt);
  77. 	return 0;
  78. }

J.翻转硬币（整除分块+杜教筛）

题面

a44b8a9e5bc144938180959d7f0df09b.png​

89912e23460645498efe890c3521effe.png​

题解

1. 5e6，可以考虑埃筛枚举因数，x需要翻当且仅当x的真因数翻了奇数次

2. 1e9，观察5e6时的式子，其实就是莫比乌斯函数gif.latex?%5Cmu%28i%29模2意义下的值，

即只有0和1两种情况，此时可以认为是gif.latex?%7C%5Cmu%28i%29%7C或gif.latex?%5Cmu%28i%29%5E%7B2%7D，然后直接套杜教筛

3. 1e18，观察1e9时的式子或思考莫比乌斯函数的定义，

只有包含完全平方因子的数的gif.latex?%5Cmu值才为0，

所以，考虑对平方因子容斥，gif.latex?%5Csum_%7Bd%3D1%7D%5E%7B%5Cleft%20%5Clfloor%20%5Csqrt%20n%20%5Cright%20%5Crfloor%7D%5Cmu%28d%29*%20%5Cleft%20%5Clfloor%20%5Cfrac%7Bn%7D%7Bd*d%7D%20%5Cright%20%5Crfloor即为所求，

即：gif.latex?%5Csum_%7Bi%3D1%7D%5En%7B%5Cmu%28i%29%5E2%7D%20%3D%20%5Csum_%7Bd%3D1%7D%5E%7B%5Cleft%20%5Clfloor%20%5Csqrt%20n%20%5Cright%20%5Crfloor%7D%5Cmu%28d%29*%20%5Cleft%20%5Clfloor%20%5Cfrac%7Bn%7D%7Bd*d%7D%20%5Cright%20%5Crfloor

当然，化到这个式子的情况下，直接暴力也是可以通过1e9的数据的

然而，对于1e18，直接整除分块（数论分块）的话是gif.latex?O%28%5Csqrt%7Bn%7D%29​的，不能接受

于是，类似杜教筛预处理gif.latex?O%28n%5E%5Cfrac%7B2%7D%7B3%7D%29​前缀和的操作，

这里实际预处理gif.latex?%28%5Csqrt%7Bn%7D%29%5E%7B%5Cfrac%7B2%7D%7B3%7D%7D​部分的答案（询问是单组的，现算这部分效果是一样的）

用杜教筛预处理gif.latex?%5Cmu的前缀和，后面[1e6,1e9]的部分用整除分块配合gif.latex?%5Cmu的区间和解决

【SSL 2402】最简根式（杜教筛）（整除分块）_SSL_TJH的博客-CSDN博客，与这个题类似

复杂度感觉是gif.latex?O%28n%5E%5Cfrac%7B1%7D%7B3%7D%29​的，但据uoj群友说是gif.latex?O%28n%5E%5Cfrac%7B2%7D%7B5%7D%29​的，就不太懂了…

实际预处理到1e6交New Online Judge也是会TLE的，改到1e7才过

代码

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N=1e7+10;
  5. bool ok[N];
  6. int pr[N],mu[N],cnt,up;
  7. map<int,int>smu;
  8. ll n,ans[N];
  9. void sieve(ll n){
  10.     mu[1]=1;
  11.     for(ll i=2;i<N;++i){
  12.         if(!ok[i]){
  13.             pr[cnt++]=i;
  14.             mu[i]=-1;
  15.         }
  16.         for(int j=0;j<cnt;++j){
  17.             ll k=i*pr[j];
  18.             if(k>=N)break;
  19.             ok[k]=1;
  20.             if(i%pr[j]==0){
  21.                 mu[k]=0;
  22.                 break; 
  23.             }
  24.             mu[k]=-mu[i];
  25.         }
  26.     }
  27.     for(int i=1;i<N;++i){
  28.     	ans[i]=mu[i]*(n/i/i);
  29.     }
  30.     for(int i=2;i<N;++i){
  31.         mu[i]+=mu[i-1];
  32.         ans[i]+=ans[i-1];
  33.     }
  34. }
  35. int djsmu(int n){
  36.     if(n<N)return mu[n];
  37.     if(smu.count(n))return smu[n];
  38.     int ans=1;
  39.     for(int l=2,r;l<=n;l=r+1){
  40.         r=n/(n/l);
  41.         ans=ans-(r-l+1)*djsmu(n/l);
  42.         if(r==n)break;
  43.     }
  44.     return smu[n]=ans;
  45. }
  46. ll cal(ll n){
  47. 	int sq=sqrt(n);
  48. 	if(sq<N)return ans[sq];
  49. 	ll l=2;
  50. 	for(;l*l*l<=n;l++);
  51. 	ll res=ans[l-1];
  52. 	for(ll r;l*l<=n;l=r+1){
  53. 	    ll v=n/l/l;
  54. 		r=sqrt(n/v);
  55. 		res+=v*(djsmu(r)-djsmu(l-1));
  56. 	}
  57. 	return res;
  58. }
  59. int main(){
  60.     scanf("%lld",&n);
  61.     sieve(n);
  62.     printf("%lld\n",cal(n));
  63.     return 0;
  64. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/406089
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号