100085G GCD Guessing Game

传送门

题目大意

给定一个数N，现在又一个数x，在1~N之间，现在每次可以猜一个数a，返回gcd(x,a),问说最少猜几次可以确定x。

分析

这个题应该可以算是贪心，但是没人知道这样为啥是对的（雾），我们现在来感性认识一下，我们知道对于任意一个数都可以写p1p2的形式，所以我们在每一次询问都可以确定有些p是否存在，如果存在我们在来确定它对应的e，这样只需要两次，而我们感性思考可以猜出没猜到一个p并确认一个e用去两次却可以直接否定很多其它的p，所以猜的次数一定小于等于确认所有p的次数，所以便可以按照下面的代码进行求解。

代码

#include<bits/stdc++.h>

using namespace std;

int dq[],L=,R=;

inline bool is(int x){

      int i;

      for(i=;i*i<=x;i++)

        if(x%i==)return ;

      return ;

}

int main(){

      freopen("gcd.in","r",stdin);

      freopen("gcd.out","w",stdout);

      int n,i,ans=;

      scanf("%d",&n);

      for(i=;i<=n;i++)

        if(is(i))

          dq[++R]=i;

      while(L<=R){

          while(dq[L]*dq[R]<=n){

            L++;

            dq[R]*=dq[L];

          }

          R--;

          ans++;

      }

      cout<<ans<<endl;

      return ;

}