题意 : 从 < = S 的 数 中 选 出 K 个 不 同 的 数 并 且 gcd > 1 。求方案数。
思路 ：记 录 一 下 每 个 数 的 倍 数 vector 存 储 ，最后从 2 开始 遍历 一遍每个数 ，从 他的倍数中 挑选 k个 组合数求解。
但是会有重复，因为 比如 K=2，S=15时 ， 2倍数 ： 2 ，4 ， 6， 8， 10， 12， 14 ， 挑出了 这种情况 6 ，12，然后
从3的倍数 ： 3， 6 ，9，12 ，15, 也选出了 6， 12 这种情况。所以产生重复计数 ，去重，通过他们的最小公倍数 6
6的倍数 ： 6， 12, 去掉 即可。 恰好符合莫比乌斯函数的相反数 作为系数。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 1234
vector<ll>p[55];
bool vis[maxn+10];
int prime[maxn+10],mu[maxn+10];
ll s,k,c[33][33],ans,len;
void init()
{
for(int i=0; i<=30; i++)c[i][0]=1;
for(int i=1; i<=30; i++)
for(int j=1; j<=i; j++)
c[i][j]=c[i-1][j-1]+c[i-1][j];
}
void getphi()
{
int cnt=0;
mu[1]=1;
for(int i=2; i<maxn; i++)
{
if(!vis[i])
{
prime[++cnt]=i;
mu[i]=-1;
}
for(int j=1; j<=cnt&&i*prime[j]<maxn; j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
{
mu[i*prime[j]]=0;
break;
}
else mu[i*prime[j]]=-mu[i];
}
}
}
int main()
{
init();
getphi();
scanf("%lld%lld",&k,&s);
for(int i=2; i<=s; i++)
for(int j=2; j<=i; j++)
if(i%j==0)p[j].push_back(i);
for(int i=2; i<=s; i++)
{
len=p[i].size();
if(len<k)continue;
ans+=(-mu[i]*c[len][k]);
}
if(ans>10000)printf("10000\n");
else printf("%lld\n",ans);
return 0;
}
直接进行计数 dp[ i ] [ j ] [ k ] 前 i 个 数 选 了 j 个 数, gcd 为 k 的 方 案 数.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 65
ll dp[maxn][maxn][maxn],ans;
int k,s;
int main()
{
scanf("%d%d",&k,&s);
for(int i=0; i<=s; i++)dp[i][1][i]=1;
for(int i=1; i<s; i++)
for(int j=1; j<=min(k,i); j++)
for(int z=1; z<=s; z++)
{
dp[i+1][j][z]+=dp[i][j][z];
dp[i+1][j+1][__gcd(i+1,z)]+=dp[i][j][z];
}
for(int i=2; i<=s; i++)
ans+=dp[s][k][i];
if(ans>10000)printf("10000\n");
else printf("%lld\n",ans);
return 0;
}