51NOD 1536 不一样的猜数游戏 数论

1536 不一样的猜数游戏 题目来源： CodeForces 基准时间限制：1 秒 空间限制：131072 KB 分值: 20 难度：3级算法题 收藏 关注 瓦斯亚和皮台亚在玩一个简单的游戏。瓦斯亚心中想一个整数x，它是1到n之间的整数。然后皮台亚尝试着猜这个数字。 皮台亚每次问一个形如这样的问题：这个x是y的倍数吗？ 这个游戏的流程是这样的：首先皮台亚把所有他想问的形如上述的问题都问出来（当然他也可以不问任何问题），然后瓦斯亚针对每一个问题给出yes或no的答案。最后皮台亚根据这些问题推断出瓦斯亚心中所想的x是哪个数字。 现在皮台亚想知道他最少要问多少个问题才能猜出1到n之间的那个数字。也就是说不管x是1到n之间的哪个数字只要问那些问题就能够确定那个数字了。 样例解释： 可以问是否是2，3，4这些数字倍数的三个问题。 如果都不是，说明是1. 如果是4的倍数，说明是4. 如果是3的倍数说明是3. 否则就是2。 没有比这更少的问题数目了。 Input 单组测试数据。 第一行输入一个整数n (1≤n≤1000)。 Output 输出最少的问题数目。 Input示例 样例输入1 4 Output示例 样例输出1 3 System Message (题目提供者)

对任意整数 a 存在唯一的 a = k1^b1 * k2^b2 * .... * kn^bn 其中 ki为素数，bi为正整数 显然 所有素数都要问一遍 如果对任意 ki^bj <= n 都问一遍 那<=n的任意一个数都能确定 因为 答案就是x = lcm(ki^bj) 其中 x 是 ki^bj 的倍数 所以一共需要问 ∑bi = ∑log(n)/log(ki)

#include<iostream> #include<stdlib.h> #include<stdio.h> #include<string> #include<vector> #include<deque> #include<queue> #include<algorithm> #include<set> #include<map> #include<stack> #include<time.h> #include<math.h> #include<list> #include<cstring> #include<fstream> #include<queue> #include<sstream> //#include<memory.h> using namespace std; #define ll long long #define ull unsigned long long #define pii pair<int,int> #define INF 1000000007 #define pll pair<ll,ll> #define pid pair<int,double> const int N = 1e3 + 5; bool isPrimer[N]; void primer(int n){ fill(isPrimer+2,isPrimer+n+1,true); for(int i=2;i<=n;++i){ for(int j = i*i;j<=n;j+=i){ isPrimer[j] = false; } } } int slove(int n){ primer(n); int ans = 0; for(int i = 2;i<=n;++i){ if(isPrimer[i]){ ans += log(n)/log(i); } } return ans; } int main() { //freopen("/home/lu/Documents/r.txt","r",stdin); //freopen("/home/lu/Documents/w.txt","w",stdout); int n; scanf("%d",&n); printf("%d\n",slove(n)); return 0; }