Codeforces Round #319 (Div. 2) C. Vasya and Petya’s Game | 书脊

Codeforces Round #319 (Div. 2) C. Vasya and Petya's Game | 书脊

Codeforces Round #319 (Div. 2) C. Vasya and Petya's Game

原题: http://codeforces.com/contest/577/problem/C

---

题目大意: 给一个数字n, 一个人猜这个n是多少, 他可以提问: n是不是整除x, 问你最少提问多少次,问的是什么可以猜出n.

---

分析: 算术基本定理(https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic). 可以证明,我们需要猜出每个n前边的的质数p, 对于每个p,我们还要猜出其不大于n的倍数, 才能确保n的唯一.

所以答案先晒质数, 再求倍数.

Read full article from Codeforces Round #319 (Div. 2) C. Vasya and Petya's Game | 书脊