T1
这个向下取整是没有用的，所以可以直接暴力 dfs。
然后要注意一下，如果数组里有 \(1\)，你需要直接跳过，不然 \(1\) 可以使用无数次。
inline int ksm(int a,int b){
int res=1;
while(b){
if(b&1)res=res*a;
a=a*a;
b>>=1;
}
return res;
}
int n,m;
vector<int>a;
unordered_map<int,int>mp;
int lim;
int ans;
inline void dfs(int u,int sum){
if(u==lim){
if(!mp[sum])mp[sum]=1,ans++;
return;
}
for(int i=0;;i++){
int t=ksm(a[u],i);
if(t>sum)break;
dfs(u+1,sum/t);
}
}
signed main(){
freopen("set.in","r",stdin);
freopen("set.out","w",stdout);
n=read();m=read();
up(i,1,m){
a.push_back(read());
}
sort(a.begin(),a.end());
a.erase(unique(a.begin(),a.end()),a.end());
lim=a.size();
if(a[0]==1)dfs(1,n);
else dfs(0,n);
if(!mp[0])ans++;
cout<<ans;
return 0;
}
T2
很有意思的一道题，题意浓缩一下，就是让你求出最长的子序列和最短的子序列分别使得序列 \(\gcd\) 为 \(1\)。
很显然，最长的子序列就是整个序列，这是很好求的，那么最短的该如何求呢？
首先，由于 \(2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19=15796638>w\)，所以这个子序列的长度一定不超过 \(7\)。
所以我们可以考虑容斥，枚举选择的个数,减去所有 \(\gcd\) 是其倍数的数。
inline int ksm(int a,int b){
int res=1;
while(b){
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int a[N],b[N];
int maxl,ans[N],f[N];
int fac[N],ifac[N];
inline void init(int n){
fac[0]=1;ifac[0]=1;
up(i,1,n)fac[i]=fac[i-1]*i;
ifac[n]=ksm(fac[n],mod-2);
dn(i,n-1,1)ifac[i]=(i+1)*ifac[i+1]%mod;
}
inline int C(int n,int m){
if(n<m)return 0;
return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int n,m;
signed main(){
n=read();m=read();
init(n);
up(i,1,n){
a[i]=read();
b[a[i]]++;
maxl=max(maxl,a[i]);
}
up(i,1,maxl){
for(int j=i*2;j<=maxl;j+=i)b[i]+=b[j];
}
up(i,1,m)ans[i]=-1;
dn(i,7,1){
dn(j,maxl,1){
f[j]=C(b[j],i);
for(int k=2*j;k<=maxl;k+=j)f[j]=(f[j]-f[k]+mod)%mod;
}
up(j,1,m){
if(f[j])ans[j]=i;
}
}
up(i,1,m){
if(ans[i]==-1)cout<<"-1 -1"<<endl;
else cout<<ans[i]<<" "<<b[i]<<endl;
}
return 0;
}