http://acm.timus.ru/problem.aspx?

space=1&num=1091

从1~s中选出k个数，使得k个数的最大公约数大于1，问这种取法有多少种。

（2<=k <= s<=50）

同素数四元组问题类似，能够參考http://blog.csdn.net/u013081425/article/details/40653895

仅仅只是这里是选出k个。不是4个。

#include <stdio.h>

#include <iostream>

#include <map>

#include <set>

#include <bitset>

#include <list>

#include <stack>

#include <vector>

#include <math.h>

#include <string.h>

#include <queue>

#include <string>

#include <stdlib.h>

#include <algorithm>

#define LL __int64

//#define LL long long

#define eps 1e-9

#define PI acos(-1.0)

using namespace std;

const int maxn = 100010;

int k,s;

int num[55];

int prime[] = {15,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};

int cnt[55];

LL c[55][55];

void init()

{

    memset(c,0,sizeof(c));

    for(int i = 1; i <= 25; i++)

    {

       for(int j = 0; j <= i; j++)

        {

            if(j == 0 || j == i)

                c[i][j] = 1;

            else if(j == 1)

                c[i][j] = i;

            else

                c[i][j] = c[i-1][j-1] + c[i-1][j];

        }

    }

}

void dfs(int st, int val, int num)

{

    if(val > 50) return;

    cnt[val] = num&1 ?

1 : -1;

    for(int i = st; i <= prime[0]; i++)

    {

        if(prime[i]*val > 50)

            break;

        dfs(i+1,val*prime[i],num+1);

    }

}

int main()

{

    init();

    memset(cnt,0,sizeof(cnt));

    dfs(1,1,0);

    while(~scanf("%d %d",&k,&s))

    {

        for(int d = 2; d <= s; d++)

        {

            num[d] =  s/d;

        }

        LL ans = 0;

        for(int d = 2; d <= s; d++)

        {

            if(num[d] < k)

                break;

            if(cnt[d])

            {

                ans += cnt[d]*c[num[d]][k];

            }

        }

        if(ans >= 10000)

            printf("10000\n");

        else

            printf("%I64d\n",ans);

    }

    return 0;

}