URAL 1091 Tmutarakan Exams(反発原理)

タイトル:
S以内にSを含んで、最大公約数が1より大きいK個の異なる数はどれだけの情況がありますかを求めます.
問題:
k個の異なる数に公約数>1を持たせるには、これらの数には必ず共通の約数n>1があることを知っています.計算を繰り返さないために、この質量数約数を列挙し、倍数の数nを得ると、この約数で得られるK個の異なる数の組み合わせ案にはC[n][K]がありますが、現在S=12、K=1と仮定すると、2,4,6,8 10,12;3 6, 9, 12;2と3の対応する組み合わせは,6,12が繰り返しであることを示した.では,反発原理に基づいて繰り返し剃ることは,2,3の最小公倍数に対応する組合せ数を剃ることである.

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define B(x) (1<<(x))
void cmax(int& a,int b){ if(b>a)a=b; }
void cmin(int& a,int b){ if(b<a)a=b; }
typedef long long ll;
const int oo=0x3f3f3f3f;
const ll OO=1LL<<61;
const int MOD=1000007;
const int maxn=55;
int p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61};
ll C[maxn][maxn];
int K,S;

void get_C(){
    for(int i=0;i<maxn;i++){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;j++)
            C[i][j]=C[i-1][j]+C[i-1][j-1];
    }
}

ll dfs(int s,int x,int n){
    ll res=0,cnt,t;
    for(int i=s;p[i]<=n;i++){
        res+=C[x/p[i]][K]-dfs(i+1,x/p[i],n);
    }
    return res;
}

ll solve(int n){
    ll ans=dfs(0,n,n);
    if(ans>10000)ans=10000;
    return ans;
}

int main(){
    //freopen("E:\\read.txt","r",stdin);
    get_C();
    while(scanf("%d %d",&K,&S)!=EOF){
        printf("%I64d
",solve(S));
    }
    return 0;
}