• [1722] Wc与整数分组

  • 时间限制: 1000 ms　内存限制: 65535 K
  • 问题描述

  • 将前n个正整数分成k组，使得每组中的正整数两两互质。求k的最小值。

    注意：两个正整数互质，指的是两个正整数的最大公因数等于1。

  • 输入
  • 第一行有一个整数T (1<=T<=1e5)，表示数据组数，对于每组数据：
    每一行只有一个整数n(1<=n<=1e9)
  • 输出
  • 每组数据输出一行一个整数，表示k的最小值
  • 样例输入
  • 2
3
4
  • 样例输出
  • 1
2
  • 提示
  • 对于第一组数据，由于1，2，3这三个数本来就两两互质，所以只要分成一组即可，即k=1。
对于第二组数据，我们可以将1，2，3，4这四个数分成1，4和2，3两组，即k=2,就能满足要求。容易发现这也是我们能获得的最小的k。

如果cin超时可以使用scanf
如果scanf使用long long ，必须使用%I64d
  • 来源
  • 本站或者转载
  • 操作

显示春菜