UncleBlack的博客通过本文主要向大家介绍了编程题等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
一个数字被称之为 2357 数，当且仅当其所有大于 1 的因子均能被 2/3/5/7 中的某一个整除。对于数字 N，你需要求出不小于 N 的最小 2357 数。
输入格式
一个数字n
输出格式
一个数字表示最小的 2357 数
样例输入
209
样例输出
210
数据范围
对于 30%的数据，N≤5000。
对于 60%的数据，N≤10^9。
对于 100%的数据，N≤10^13。
看到这道题第一个反应是找规律，毕竟一般来说找数的题都会存在规律而言，而且数据范围又这么大，应该来说是一个很朴素的公式。但是找了半天发现没有什么规律，在考试的时候并没有想出有什么好的方法求解，于是就来了个60分的暴力算法骗分
#include<iostream>
using namespace std;
bool find(long long x)
{
while(x%2==0)x/=2;
while(x%3==0)x/=3;
while(x%5==0)x/=5;
while(x%7==0)x/=7;
if(x==1)return true;
else return false;
}
int main()
{
long long n,t;
cin>>n;
while(!find(n))n++;
cout<<n;
}
上面这个代码是个60分的暴力代码，因为循环次数太多，所以说到后面大数据的时候会超时，需要用更优秀的代码来优化。这里提供三个方法。
方法一：暴力枚举2,3,5,7的各个次数。
考试的时候我也想到了这个问题，2，3 , 5 , 7这四个数比较特殊，它们随意乘起来可以组成任何的非素数以及非因数中含有素数的数。对于题目范围中的10^13的数据范围，我们可以尝试着枚举2,3,5,7的次数，枚举的范围;2有45次左右，3有29次左右，5有20次左右，7有16次左右。45*29 *20 *16==417600，加上快速幂（log2(b)）也不会超时。
#include<cstdio>
#include<algorithm>
using namespace std;
long long data[1000000];
long long KSM(long long a,long long b)
{
long long ans=1;
while(b)
{
if(b&1) ans*=a;
b>>=1;
a*=a;
}
return ans;
}
int main()
{
long long n,a,b,c,d,ans,Case=0;
scanf("%lld",&n);
for(d=0;d<=16;d++)
for(c=0;c<=20;c++)
for(b=0;b<=29;b++)
for(a=0;a<=45;a++)
{
ans=KSM(2,a)*KSM(3,b)*KSM(5,c)*KSM(7,d);
if(ans>=n && ans<3*n)
data[++Case]=ans;
if(ans>=3*n)
break;
}
long long Min=100000000000000LL;
for(int i=1;i<=Case;i++)
if(data[i]<Min)
Min=data[i];
printf("%lld\n",Min);
return 0;
}
方法二：单调/优先队列
直接上代码，依次讨论2.3.5.7的情况就可以了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#define LL long long
using namespace std;
inline void du(LL &d)
{
char t=getchar(); bool mark=false;
for(;t<'0'||t>'9';t=getchar())if(t=='-')mark=!mark;
for(d=0;t>='0'&&t<='9';t=getchar())d=d*10+t-'0';
if(mark)d=-d;
}
LL n;
deque<LL> Q1,Q2,Q3,Q4;
LL get_front()
{
LL a,b,c,d,ans;
a=Q1.front();
b=Q2.front();
c=Q3.front();
d=Q4.front();
ans=min(min(a,b),min(c,d));
if(a==ans)Q1.pop_front();
if(b==ans)Q2.pop_front();
if(c==ans)Q3.pop_front();
if(d==ans)Q4.pop_front();
return ans;
}
int main()
{
du(n);
if(n==1){cout<<1;return 0;}
LL t=n<<1;
Q1.push_back(2);
Q2.push_back(3);
Q3.push_back(5);
Q4.push_back(7);
LL p=2;
while(p<n)
{
Q1.push_back(p*2);
if(p*3<t)Q2.push_back(p*3);
if(p*5<t)Q3.push_back(p*5);
if(p*7<t)Q4.push_back(p*7);
p=get_front();
}
cout<<p;
}
方法三:搜索
我觉得很玄幻，搜索也能过而且不超时，也算是很厉害，代码如下，比其他代码短多了~
#include<iostream>
#include<cstdio>
#define ll long long
const ll inf=99999999999999LL;
using namespace std;
ll ans=inf,n;
int a[5]={0,2,3,5,7};
void dfs(ll x,ll t)
{
if(x>=n)
{
ans=min(x,ans);
return ;
}
if(t>4)return ;
for(ll i=x;i<=ans;i*=a[t])dfs(i,t+1);
}
int main()
{
scanf("%lld",&n);
dfs(1,1);
printf("%lld",ans);
}