牛客手速月赛40 H

题目

题意: 给定一个有 n个元素的多重集 S，有 m个询问，对于每个询问，给出一个整数 x，问是否能选择 S 的一个非空子集，满足这个子集的 gcd等于x，当集合只有一个数时，设这个集合的 gcd 就等于这个数

思路: 显然，满足gcd为x的子集，满足所有数都是x的倍数。而且，gcd是数越多越有可能变小。所以，不妨模仿一下埃氏筛，预处理一下。对于每个数i,判断S中所有i的倍数能否通过gcd得到。 时间复杂度: nlnn,调和级数

代码:

// Problem: 来点gcd
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11217/H
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i