如何求出从2到N+1的群总数
在特定的社交网络中，朋友由系统自动分配给用户，用户不能自行添加自己选择的好友。目前社交网络上有N个用户，标记为2到N+ 1。对于每一个I-用户(我的范围从2到N+ 1)，系统将所有标记为i的用户分配为用户的朋友(如果可能的话)。有一天，社交网络的所有用户聚在一起开会，组成一个团体，这样一个团体中的每一个人都是该群体中每一个人的直接朋友或朋友。
示例:输入: 10
产出:3
解释：
将组成三个组：{2、3、4、5、6、8、9、10}、{7}和{11}
回答 9
Stack Overflow用户
发布于 2020-03-04 15:27:13
输入：10
成员：{2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
直接好友：(以i的倍数标记为用户朋友的用户)
2 --> {4, 6, 8, 10}
3 --> {6, 9}
4 --> {2, 8}
5 --> {10}
6 --> {2, 3}
7 --> {}
8 --> {2, 4}
9 --> {3}
10 --> {5}
11 --> {}朋友的朋友：(朋友集合的所有朋友的联盟-直接朋友。)
2 --> {3, 5}说明:直接朋友，2 --> {4, 6, 8, 10}
所以,
{2, 8} U {2, 3} U {2, 4} U {5} - {4, 6, 8, 10}
= {2, 3, 4, 5, 8} - {4, 6, 8, 10}
= {3, 5}移除2本身。
类似地，
3 --> {2}
4 --> {6, 10}
5 --> {2}
6 --> {4, 8, 9, 10}
7 --> {}
8 --> {6, 10}
9 --> {6}
10 --> {}
11 --> {}现在分组
以第一个直接朋友组{2, 4, 6, 8, 10}为例，现在添加每个成员的直接朋友或朋友的朋友
={2, 3, 4, 5, 6, 8, 10}从成员集( {7, 11} )中删除所有这些
他们没有朋友，所以他们分成两组：{7}和{11}。
因此，我们有三个组。。。
输入：5
成员：{2, 3, 4, 5, 6}
直接朋友：
2 --> {4, 6}
3 --> {6}
4 --> {2}
5 --> {}
6 --> {3}朋友的朋友：(朋友集合的所有朋友的联盟-直接朋友.)
2 --> {3}
3 --> {2}
4 --> {6}
5 --> {}
6 --> {}现在分组：
作为第一个直接朋友小组，
{2, 4, 6}, now adding every members direct friend or friend of friends
={2, 3, 4, 6}从成员集( {5} )中删除所有这些
As a result, we have 2 groups.Implementation:
Java HashSet是实现它的一个很好的选择。
我认为这个解释一开始就足够好。如果您在实现方面有问题，请在这里询问。
--我已经实现了，下面是一些示例输入/输出：
Input: N = 4
Total Groups: 3
Groups: [[3], [5], [2, 4]]
Input: N = 10
Total Groups: 3
Groups: [[7], [11], [2, 3, 4, 5, 6, 8, 9, 10]]
Input: N = 13
Total Groups: 3
Groups: [[2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14], [11], [13]]
Input: N = 20
Total Groups: 5
Groups: [[17], [19], [2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21], [11], [13]]Stack Overflow用户
发布于 2020-09-14 08:53:10
除了没有任何小于N+1的素数外，所有用户都属于同一组，最小的倍数为2*(素数)，所以如果n+1 < 2*prime_number，则增加组数。C++溶液->
#include <bits/stdc++.h>
using namespace std;
bool checkPrime(int num)
{
for(int i=2; i<=sqrt(num); i++)
{
if(num%i == 0) return false;
}
return true;
}
int main()
{
int n;
cin >> n;
int ans = 1;
for(int i = 2; i <= n + 1; i++)
if(checkPrime(i) && i * 2 > n + 1) ans++;
if(n <= 2) ans--;
cout << ans << endl;
return 0;
}Stack Overflow用户
发布于 2020-03-04 15:52:11
另一种方法是基于以下观察：
A user will either be in a group with "2" or be in a group by himself在此基础上，可以导出所有用户x ( x > N/2和x为素数)将位于一个单用户组中，而所有其他用户将形成一个2的组。
https://stackoverflow.com/questions/60527097
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号