70pts #8,9,10TLE 求助大佬!
查看原帖
70pts #8,9,10TLE 求助大佬!
961823
qinjinnan楼主2023/11/2 18:51

在代码里面加了注释

#include<bits/stdc++.h>
using namespace std;
const int N=20000000;

int a[N],a7[N];//a数组存放能不能报,a7存放数里有没有7,记忆化(bushi
//a中:-1表示没有做到,0表示不能报,1表示能报
//a7中:-1表示没有做到,0表示没有7,1表示有7

int check7(int b)//判断数字有没有7
{
	if(a7[b]!=-1)return a7[b];//做过了就直接返回
	int i=0;
	while(b!=0)
	{
		i=b%10;
		if(i==7)
		{
			a7[b]=1;
			return 1;
		}
		b/=10;
	}
	a[b]=0;//记忆
	return 0;
}

int work1(int n)//判断因数里面有没有含7的
{
	if(a[n]!=-1)return a[n];
	for(int i=1;i<=sqrt(n);i++)
	{
		if(n%i==0)
		{
			if(check7(i) or check7(n/i))
			{
				a[n]=0;
				return 0;
			}
		}
	}
	a[n]=1;
	return 1;
}

int work(int n)//查找
{
	if(work1(n)==0)return -1;
	int i=n+1;
	while(work1(i)==0)i++;
	return i;
}

int main()
{
//	freopen("number.in","r",stdin);
//	freopen("number.out","w",stdout);
	
	memset(a,-1,sizeof(a));
	memset(a7,-1,sizeof(a7));
	int n,m;
	cin>>n;
	for(int j=1;j<=n;j++)
	{
		cin>>m;
		cout<<work(m)<<endl;
	}
	return 0;
}
2023/11/2 18:51
加载中...