2017-10-31 15:12

# Coffee shop in Jioufen

Problem Description
Cheer manages a coffee shop in Jioufen. As she is the only assistant in the shop, it is a big problem for her to mix up raw materials into a cup of coffee.
To simplify the problem, we can assume that Cheer has n kinds of raw material, and the i-th raw material has been assigned with a value ai denoting its level of deliciousness.
For some unknown reason, Cheer believe that a kind of coffee is perfect if and only if the value of its all kinds of raw materials are co-prime with each other. A kind of perfect coffee also can be made without any of these raw materials, only by water.
Now given n kinds of raw material and their value of deliciousness, find out how many distinct kinds of perfect coffee can be made by them. Note that two kinds of coffee are considered distinct if and only if the raw material sets of them are distinct.

Input
There are at most 75 test cases.
For each case, The first line contains one integer n indicating the number of kind of raw material.
The next line contains n integers separated by space, denoting deliciousness values: a1, a2, ..., an
(1 <= n <= 60, 1 <= ai <= 231-1)
The input ends with n = 0

Output
For each test case, print the number of distinct kind of prefect coffee she can made in one line.

Sample Input
2
2 2
3
1 2 3
3
2 3 4
0

Sample Output
3
8
6

• 点赞
• 写回答
• 关注问题
• 收藏
• 复制链接分享
• 邀请回答

#### 2条回答

• devmiao 4年前
• qq_40723276 4年前

有两种方法。
一个是全局发号器（例如ZooKeeper有Sequence型节点，或者自己弄个发号器服务不断产生递增值作为发号），但是效率会比较低。
二个是mapPartition，获得当前分区的分区号。然后分区号x一个系数+当前分区本地递增值。系数是分区最大的数据条数+一定冗余。
最省事是前者，最快但容易出问题是后者。

点赞 评论 复制链接分享