NOIP 2021 第一题 报数 number 游走在超时的边缘(不定长数组) 10分+30分+50分(纯暴力)+70分(约数范围缩到sqrt(x)之内 4倍2倍重复的筛法 )+100分(查找优化)

总目录详见：NOIP 提高组 复赛 试题 目录 信奥 历年

在线测评地址：洛谷 P7960 [NOIP2021] 报数

1.10分

对于10% 的数据，T≤10，x≤100。

纯暴力，极限情况，在x=100中傻傻找约数,1,2,3,......,99,100的方式，查找100次，再对约数进行判定，约数中数字是否含有7(极限是每个约数2次)，约数是否是7的倍数(极限是每个约数1次)，故此时对于每个极限计算次数是100*(2+1)=300，这是找一个数的情况，在x≤100中，对应最多找数的情况，要编写代码测试，之后，才知道，预计下一个符合条件的数字间隔最大在11左右。因极限情况T=10，总次数是300*11*10=33000，不超时。

后记，可以手工算出110内的数据，打上标记，程序进行处理，10分就拿到了。

2.30分

对于 30% 的数据，T≤100，x≤1000。

纯暴力，极限情况，在x=1000中傻傻找约数,1,2,3,......,999,1000的方式，查找1000次，再对约数进行判定，约数中数字是否含有7(极限是每个约数3次)，约数是否是7的倍数(极限是每个约数1次)，故此时对于每个极限计算次数是1000*(3+1)=4000，这是找一个数的情况，在x≤1000中，对应最多找数的情况，要编写代码测试，之后，才知道，预计下一个符合条件的数字间隔最大在11左右。因极限情况T=100，总次数是4000*11*100=4400000，不超时。

50分代码如下：

#include <bits/stdc++.h>
using namespace std;
bool find7(int a){//判断数a是否被7整除,是否某位上包含7 if(a%7==0)return 1;while(a){//分析个,十,百,千,等位上数字 if(a%10==7)return 1;a/=10;}return 0;//与7无关. 
}
bool isBad(int x){//判断x中所有因数是否包含7 int a;for(a=1;a<=x;a++){if(x%a==0){//a是约数 if(find7(a)==1){break;} }}if(a==x+1)return 0;//x中不包含7 else return 1;//x中包含有7 
}
int main(){int t,x,a,b;scanf("%d",&t);while(t--){scanf("%d",&x);if(isBad(x)==1)printf("-1\n");else{//查找下一个有效while(1){x++;if(isBad(x)==0){printf("%d\n",x);break;}}}}return 0;
} 

3.50分

对于 50% 的数据，T≤1000，x≤10000。

纯暴力，极限情况，在x=10000中傻傻找约数,1,2,3,......,9999,10000的方式，查找10000次，再对约数进行判定，约数中数字是否含有7(极限是每个约数5次)，约数是否是7的倍数(极限是每个约数1次)，故此时对于每个极限计算次数是10000*(5+1)=60000，这是找一个数的情况，在x≤10000中，对应最多找数的情况，要编写代码测试，之后，才知道，预计下一个符合条件的数字间隔最大在11左右。因极限情况T=1000，总次数是60000*11*1000=6.6*10^8，超时不可避免。

纯暴力，极限情况，改进在x=10000约数,1,2,3,......,9999,10000的方式，按1,2,3,......,sqrt(100000)查找100次，再对约数进行判定，约数中数字是否含有7(极限是每个约数5次)，约数是否是7的倍数(极限是每个约数1次)，因找到一个约数，另一个约数也就找到了,故此时对于每个极限计算次数是2*100*(5+1)=1200，这是找一个数的情况，在x≤10000中，对应最多找数的情况，要编写代码测试，之后，才知道，预计下一个符合条件的数字间隔最大在11左右。因极限情况T=1000，总次数是1200*11*1000=1.32*10^7，预计处于超时，或不超时的临界状态。

70分代码如下：

#include <bits/stdc++.h>
using namespace std;
bool find7(int a){//判断数a是否被7整除,是否某位上包含7 if(a%7==0)return 1;while(a){//分析个,十,百,千,等位上数字 if(a%10==7)return 1;a/=10;}return 0;//与7无关. 
}
bool isBad(int x){//判断x中所有因数是否包含7 int a,b,c;b=sqrt(x);for(a=1;a<=b;a++){if(x%a==0){//a是约数 c=x/a;//c也是约数 if(find7(a)==1||find7(c)==1){break;} }}if(a==b+1)return 0;//x中不包含7 else return 1;//x中包含有7 
}
int main(){int t,x,a,b;scanf("%d",&t);while(t--){scanf("%d",&x);if(isBad(x)==1)printf("-1\n");else{//查找下一个有效while(1){x++;if(isBad(x)==0){printf("%d\n",x);break;}}}}return 0;
} 

4.70分

对于 70% 的数据，T≤10000，x≤2×10^5。

纯暴力，极限情况，改进在x=200000，约数,1,2,3,......,199999,2*100000的方式，按1,2,3,......,sqrt(200000)查找447次，再对约数进行判定，约数中数字是否含有7(极限是每个约数5次)，约数是否是7的倍数(极限是每个约数1次)，因找到一个约数，另一个约数也就找到了,故此时对于每个极限计算次数是2*447*(6+1)=6258，这是找一个数的情况，在x≤200000中，对应最多找数的情况，要编写代码测试，之后，才知道，预计下一个符合条件的数字间隔最大在11左右。因极限情况T=10000，总次数是6258*11*10000=688380000=6.9*10^8，预计处于超时状态。

怎么改进，联想到桶排序，将2*10^5中的数据全部标记，这样就与查询次数无关了。但是每个数据都进行标记,极限情况，在x=200000，约数,1,2,3,......,199999,2*100000的方式，按1,2,3,......,sqrt(200000)查找447次，再对约数进行判定，约数中数字是否含有7(极限是每个约数5次)，约数是否是7的倍数(极限是每个约数1次)，因找到一个约数，另一个约数也就找到了,故此时对于每个极限计算次数是2*447*(6+1)=6258，这是找一个数的情况，在x≤200000中，最多有200000个数据。总次数是6258**200000=1.2516*10^9，超时了，在查找过程中，效率太低，有太多的重复。

该思路在测试大样例时，有太多的遗漏，那就作为脚印留下，读者可以跳过(如何提高效率，这时，线性筛素数浮现出来，把因数是7的数据标记出来，把某位上数据是7的数据标记出来，再由这两种数据派生出来的数据，继续标记出来。类似愚公移山，子又生孙，孙又生子......。因数是7的数据好标记，在生成合数时，就标记出来，那某位上数据是7时，如何标记，考虑了一下，在生成合数时，判断，并标记。x=200000，最多计算5次，200000个数据，最多计算次数200000*5=1*10^6，稳过70分。想的时候是这样，编码的时候，发现标记7*其他数据生成的新数据是，就已包含了上述两种情况，所以，200000个数据，最多计算次数200000*1=2*10^5.

线性筛素数有些模糊了，不过，好在当时学习时，是手动模拟过找出100里面的25个素数，磕磕碰碰，还是能编写出来。

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

一旦上面的25个素数找出来了，也就意味素数筛，编写成功了。

在测试过程中，发现，包含7的素数也要筛出来，因素数的数量不多，最大值很大时，通常不到最大值的十分之一，故算法的时间复杂度还是O(n).)

该思路在实际操作过程中，还是有数据的遗漏，决定删除(如何提高效率，这时，线性筛素数浮现出来，把因数是7的数据标记出来，把某位上数据是7的数据标记出来，生成新的数时，判定数位上是否包含7，是否能整除前面标记出因数是7或数位上是7的数。x=200000时,最多的数大约需要计算次数,数位上是6次，找因数是sqrt(200000)=447次，总的是6+447=453次，考虑到因数是7或数位上是7的数比较空洞，实际计算次数在50次左右，总的计算次数50*200000=10^7，介于超时与不超时间，还是有一定风险。

线性筛素数有些模糊了，不过，好在当时学习时，是手动模拟过找出100里面的25个素数，磕磕碰碰，还是能编写出来。

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

一旦上面的25个素数找出来了，也就意味素数筛，编写成功了。

在测试过程中，发现，包含7的素数也要筛出来，因素数的数量不多，最大值很大时，通常不到最大值的十分之一，故算法的时间复杂度还是O(n).)

很遗憾，提交，只有50分。)

50分代码如下：

#include <bits/stdc++.h>
#define maxn 210010 
using namespace std;
int prime[maxn/10],tot=0,d[maxn],seven[maxn/10],cnt=0; 
bool find7(int a){//判断数a是否某位上包含7 while(a){//分析个,十,百,千,等位上数字 if(a%10==7)return 1;a/=10;}return 0;//与7无关. 
}
void linear(int x){//线性筛素数 int i,j,k;for(i=2;i<=x;i++){if(d[i]==0){prime[++tot]=i;if(find7(i)==1)d[i]=2,seven[++cnt]=i;//素数中包含7的标记 }for(j=1;j<=tot&&i*prime[j]<=x;j++){if(d[i]==2||d[prime[j]]==2||find7(i*prime[j])==1)d[i*prime[j]]=2;//子又生孙,孙又生子else{for(k=1;k<=cnt&&seven[k]*seven[k]<=i*prime[j];k++)if(i*prime[j]%seven[k]==0){//判别当前数据是否包含7的内容 d[i*prime[j]]=2;break;}if(d[i*prime[j]]==0)d[i*prime[j]]=1;}  }}
} 
int main(){int t,x,a,b;linear(210000);scanf("%d",&t);while(t--){scanf("%d",&x);if(d[x]==2)printf("-1\n");else{x++;//下一个数据 while(d[x]==2)x++;printf("%d\n",x);}}return 0;
} 

猜测是数据溢出，加了long long后，还是50分代码如下：

#include <bits/stdc++.h>
#define maxn 210010 
using namespace std;
int prime[maxn/10],tot=0,d[maxn],seven[maxn/10],cnt=0; 
bool find7(int a){//判断数a是否某位上包含7 while(a){//分析个,十,百,千,等位上数字 if(a%10==7)return 1;a/=10;}return 0;//与7无关. 
}
void linear(int x){//线性筛素数 int i,j,k;for(i=2;i<=x;i++){if(d[i]==0){prime[++tot]=i;if(find7(i)==1)d[i]=2,seven[++cnt]=i;//素数中包含7的标记 }for(j=1;j<=tot&&i*prime[j]<=x;j++){if(d[i]==2||d[prime[j]]==2||find7(i*prime[j])==1)d[i*prime[j]]=2;//子又生孙,孙又生子else{for(k=1;k<=cnt&&(long long)seven[k]*seven[k]<=i*prime[j];k++)if(i*prime[j]%seven[k]==0){//判别当前数据是否包含7的内容 d[i*prime[j]]=2;break;}if(d[i*prime[j]]==0)d[i*prime[j]]=1;}  }}
} 
int main(){int t,x,a,b;linear(210000);scanf("%d",&t);while(t--){scanf("%d",&x);if(d[x]==2)printf("-1\n");else{x++;//下一个数据 while(d[x]==2)x++;printf("%d\n",x);}}return 0;
} 

决定采用另一种形式的筛法，发现一个有7的数据，马上，将之后的倍数打上标记，直到最大值。统计后，发现x<=210000里有179271个含7的数据，在x<=210000生成这些数据，需要562576次，70分，稳过。

以下为统计代码：

#include <bits/stdc++.h>
#define maxn 210010 
using namespace std;
int d[maxn]; 
bool find7(int a){//判断数a是否某位上包含7 while(a){//分析个,十,百,千,等位上数字 if(a%10==7)return 1;a/=10;}return 0;//与7无关. 
}
void shaker(int x){//筛子 int i,j,tot=0;for(i=1;i<=x;i++){if(find7(i)==1){for(j=1;i*j<=x;j++)d[i*j]=7,tot++;//统计总运行次数 }} printf("%d\n",tot);
} 
int main(){int t,x,a,b,cnt=0;shaker(210000);for(int i=1;i<=210000;i++)if(d[i]==7)cnt++;printf("%d\n",cnt);//统计生成含7的有效数据个数 scanf("%d",&t);while(t--){scanf("%d",&x);if(d[x]==7)printf("-1\n");else{x++;//下一个数据 while(d[x]==7)x++;printf("%d\n",x);}}return 0;
} 

以下为70分代码：

#include <bits/stdc++.h>
#define maxn 210010 
using namespace std;
int d[maxn]; 
bool find7(int a){//判断数a是否某位上包含7 while(a){//分析个,十,百,千,等位上数字 if(a%10==7)return 1;a/=10;}return 0;//与7无关. 
}
void shaker(int x){//筛子 int i,j,tot=0;for(i=1;i<=x;i++){if(find7(i)==1){for(j=1;i*j<=x;j++)d[i*j]=7;}} 
} 
int main(){int t,x,a,b;shaker(210000);scanf("%d",&t);while(t--){scanf("%d",&x);if(d[x]==7)printf("-1\n");else{x++;//下一个数据 while(d[x]==7)x++;printf("%d\n",x);}}return 0;
} 

5.100分

对于100% 的数据，T≤2×10^5，x≤10^7。

决定采用另一种形式的筛法，发现一个有7的数据，马上，将之后的倍数打上标记，直到最大值。统计后，发现x<=10001000里有9237439个含7的数据，在x<=10001000生成这些数据，需要44890674次，提交是100分，还是超时0分，胆颤心惊。

以下为统计代码：

#include <bits/stdc++.h>
#define maxn 10001010 
using namespace std;
int d[maxn]; 
bool find7(int a){//判断数a是否某位上包含7 while(a){//分析个,十,百,千,等位上数字 if(a%10==7)return 1;a/=10;}return 0;//与7无关. 
}
void shaker(int x){//筛子 int i,j,tot=0;for(i=1;i<=x;i++){if(find7(i)==1){for(j=1;i*j<=x;j++)d[i*j]=7,tot++;//统计总运行次数 }} printf("%d\n",tot);
} 
int main(){int t,x,a,b,cnt=0;shaker(10001000);for(int i=1;i<=10001000;i++)if(d[i]==7)cnt++;printf("%d\n",cnt);//统计生成含7的有效数据个数 scanf("%d",&t);while(t--){scanf("%d",&x);if(d[x]==7)printf("-1\n");else{x++;//下一个数据 while(d[x]==7)x++;printf("%d\n",x);}}return 0;
} 

以下为70分代码：

#include <bits/stdc++.h>
#define maxn 10001010 
using namespace std;
int d[maxn]; 
bool find7(int a){//判断数a是否某位上包含7 while(a){//分析个,十,百,千,等位上数字 if(a%10==7)return 1;a/=10;}return 0;//与7无关. 
}
void shaker(int x){//筛子 int i,j,tot=0;for(i=1;i<=x;i++){if(find7(i)==1){for(j=1;i*j<=x;j++)d[i*j]=7,tot++;//统计总运行次数 }} printf("%d\n",tot);
} 
int main(){int t,x,a,b,cnt=0;shaker(10001000);for(int i=1;i<=10001000;i++)if(d[i]==7)cnt++;printf("%d\n",cnt);//统计生成含7的有效数据个数 scanf("%d",&t);while(t--){scanf("%d",&x);if(d[x]==7)printf("-1\n");else{x++;//下一个数据 while(d[x]==7)x++;printf("%d\n",x);}}return 0;
} 

目前这种思路，比赛时，所有数据都超时，怎么办呢，稳妥的办法，就是比赛时存储x数据，找出最大值，根据最大值，进行筛法，以及开不定长数组vector。

以下为肯定能得70分的代码，不存在，小数据时，就超时的可能。

#include <bits/stdc++.h>
using namespace std;
vector<int> d;
int ask[200010],tot=0; 
bool find7(int a){//判断数a是否某位上包含7 while(a){//分析个,十,百,千,等位上数字 if(a%10==7)return 1;a/=10;}return 0;//与7无关. 
}
void shaker(int x){//筛子 int i,j,tot=0;for(i=0;i<=x;i++)d.push_back(0);//开拓不定长数组，最大长度 for(i=1;i<=x;i++){if(find7(i)==1){for(j=1;i*j<=x;j++)d[i*j]=7;}} 
} 
int main(){int t,x,a,b,mx=-1,T;scanf("%d",&t);T=t;while(T--){scanf("%d",&x);ask[++tot]=x,mx=max(mx,x);}shaker(mx+1000);tot=0;while(t--){x=ask[++tot];if(d[x]==7)printf("-1\n");else{x++;//下一个数据 while(d[x]==7)x++;printf("%d\n",x);}}return 0;
} 

 继续想100分代码......

考虑记录中间生成含7的数据，再次遇到此类数据，就不再派生了，这样，应能大大减少重复计算。

 70分代码如下：

#include <bits/stdc++.h>
using namespace std;
vector<int> d;
int ask[200010],tot=0; 
bool find7(int a){//判断数a是否某位上包含7 while(a){//分析个,十,百,千,等位上数字 if(a%10==7)return 1;a/=10;}return 0;//与7无关. 
}
void shaker(int x){//筛子 int i,j,tot=0;for(i=0;i<=x;i++)d.push_back(0);//开拓不定长数组，最大长度 for(i=1;i<=x;i++){if(find7(i)==1&&d[i]==0){//避免重复计算 for(j=1;i*j<=x;j++)d[i*j]=7;}} 
} 
int main(){int t,x,a,b,mx=-1,T;scanf("%d",&t);T=t;while(T--){scanf("%d",&x);ask[++tot]=x,mx=max(mx,x);}shaker(mx+1000);tot=0;while(t--){x=ask[++tot];if(d[x]==7)printf("-1\n");else{x++;//下一个数据 while(d[x]==7)x++;printf("%d\n",x);}}return 0;
} 

重新用定长数组，并改变d[i]==0的位置

#include <bits/stdc++.h>
#define maxn 10001010 
using namespace std;
int d[maxn]; 
bool find7(int a){//判断数a是否某位上包含7 while(a){//分析个,十,百,千,等位上数字 if(a%10==7)return 1;a/=10;}return 0;//与7无关. 
}
void shaker(int x){//筛子 int i,j,tot=0;for(i=1;i<=x;i++){if(d[i]==0&&find7(i)==1){for(j=1;i*j<=x;j++)d[i*j]=7;}} 
} 
int main(){int t,x,a,b;shaker(10001000);scanf("%d",&t);while(t--){scanf("%d",&x);if(d[x]==7)printf("-1\n");else{x++;//下一个数据 while(d[x]==7)x++;printf("%d\n",x);}}return 0;
} 

计算次数代码如下：

tot=16751956
cnt=7203036

#include <bits/stdc++.h>
#define maxn 10001010 
using namespace std;
int d[maxn],cnt=0; 
bool find7(int a){//判断数a是否某位上包含7 while(a){//分析个,十,百,千,等位上数字 if(a%10==7)return 1;a/=10;cnt++;}return 0;//与7无关. 
}
void shaker(int x){//筛子 int i,j,tot=0;for(i=1;i<=x;i++){if(d[i]==0&&find7(i)==1){for(j=1;i*j<=x;j++)d[i*j]=7,tot++;}} printf("tot=%d\n",tot);
} 
int main(){int t,x,a,b;shaker(10001000);printf("cnt=%d\n",cnt);scanf("%d",&t);while(t--){scanf("%d",&x);if(d[x]==7)printf("-1\n");else{x++;//下一个数据 while(d[x]==7)x++;printf("%d\n",x);}}return 0;
} 

应该来说，此种算法已经走到黑了，100分拿不了了，怎么办，只能换算法了。

结果是优化，我们用 nx 数组（也就是 next 的缩写）来记录该数的下一个报的数是多少。在处理的时候，我们需要记录上一个报的数pos（position 的缩写，也就是没有标记的数）。如果i没有标记过也不含有数字 7，那么 nx[pos] 就是i，然后将 pos更新为 i。

100分代码如下：

空间计算:int 占4个字节,(10001010*4+10001010*4)/1024/1024= 76.3MB

#include <bits/stdc++.h>
#define maxn 10001010 
using namespace std;
int d[maxn],nx[maxn],pos=0; 
bool find7(int a){//判断数a是否某位上包含7 while(a){//分析个,十,百,千,等位上数字 if(a%10==7)return 1;a/=10;}return 0;//与7无关. 
}
void shaker(int x){//筛子 int i,j,tot=0;for(i=1;i<=x;i++){if(d[i]==0&&find7(i)==1){for(j=1;i*j<=x;j++)d[i*j]=7;}if(d[i]==0){//优化，直接记录有效的数据，链表的形式 nx[pos]=i;pos=i;}} 
} 
int main(){int t,x,a,b;shaker(10001000);scanf("%d",&t);while(t--){scanf("%d",&x);if(d[x]==7)printf("-1\n");else{printf("%d\n",nx[x]);//优化 }}return 0;
} 

最稳妥的100分代码，不定长数组，链表优化。

#include <bits/stdc++.h>
using namespace std;
vector<int> d,nx;
int ask[200010],pos=0; 
bool find7(int a){//判断数a是否某位上包含7 while(a){//分析个,十,百,千,等位上数字 if(a%10==7)return 1;a/=10;}return 0;//与7无关. 
}
void shaker(int x){//筛子 int i,j;for(i=0;i<=x;i++)d.push_back(0),nx.push_back(0);//开拓不定长数组，最大长度 for(i=1;i<=x;i++){if(d[i]==0&&find7(i)==1){//避免重复计算 for(j=1;i*j<=x;j++)d[i*j]=7;}if(d[i]==0){nx[pos]=i;pos=i;}} 
} 
int main(){int t,x,a,b,mx=-1,T,tot=0;scanf("%d",&t);T=t;while(T--){scanf("%d",&x);ask[++tot]=x,mx=max(mx,x);}shaker(mx+1000);tot=0;while(t--){x=ask[++tot];if(d[x]==7)printf("-1\n");else{printf("%d\n",nx[x]);}}return 0;
}