参天大树 Problem ID: 5602怎么做

题目描述:

丛林中矗立着一棵参天大树,高度为 y。

大树 2~p 高度处,每个位置都有一只蚱蜢。

一只蚱蜢如果在 x 高度处,那么它可以跳到 2x、3x、4x、… 等任意一个 x 的倍数处。

你想在 2~y 高度范围内,找到一个尽可能高且不会有任何蚂蚱能跳到的位置。

注意你和蚂蚱的位置都必须是整数,如果你找不到任何一个合法的位置的话,就输出-1。

输入格式:

第一行包含两个正整数 p 和 y。

输出格式:

输出一行一个整数表示答案。

样例输入:

3 6

样例输出:

5

样例输入:

3 4

样例输出:

-1

数据规模:

2 ≤ p ≤ y ≤ 109
TLE代码:

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
using namespace std;
long long p,y;
map<long long,long long>m;
int main()
{
    cin>>p>>y;long long c=1,a=0;
    for(long long i=2;i<=y;i++)
    {   
        if(!m[i])m[c++]=i;
        for(long long j=1;j<=c;j++)
        {
            if(i*m[j]>y)break;
            m[i*m[j]]=1;
            if(i%m[j]==0)break;
        }
    }if(m[c-1]<=p)cout<<-1;
    else cout<<m[c-1];return 0;
}

不会啊

1 个赞

位置小于 p 的肯定已经有蚱蜢了,可以剪枝剪掉。然后再找蚱蜢的位置判断是否是当前位置的因数,如果是那就能跳到。为了找尽量高可以从上往下遍历。

2 个赞

我试试

1 个赞

谢谢,AC了

1 个赞