URAL 1091. Tmutarakan Exams-白红宇

URAL 1091. Tmutarakan Exams

阅读量：4286 次

发布时间：2019-05-27

本文共 992 字，大约阅读时间需要 3 分钟。

题意：给你两个数K，S，让你从1~S中挑选K个数使得他们的最大公约数大于1，问你有多少种方法？（如果方法大于10000 即方法就是10000）

题解：S 的范围【2,50】比较小，可以用容斥原理做

（1）把S分解素因子只需到23即可.....（组成的因子不超过S的一半）然后去能整除素因子的个数组合

（2）去除含有共同的数的组合即可 2 * 3 2 * 5 2 * 7 3 * 5 3 * 7 2 * 11 （这个可以思考一下）

code：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;typedef long long LL;int prime[9] = {2,3,5,7,11,13,17,19,23};int Ro[6] = {6,10,14,15,21,22};int C[30][30];void init(){//组合数打表    C[0][0] = 1;    for(int i = 1;i <= 25;i++)    {        C[i][0] = C[i][i] = 1;        for(int j = 1;j < i;j++)            C[i][j] = C[i-1][j-1] + C[i-1][j];    }}int main(){    init();    int K,S;    while(cin >> K >> S){        int sum = 0;        for(int i = 0;i < 9;i++){//素因子            int k = S / prime[i];            if(k >= K) sum += C[k][K];        }        for(int i = 0;i < 6;i++){//含有共同的数            int k = S / Ro[i];            if(k >= K) sum -= C[k][K];        }        if(sum > 10000) sum = 10000;        cout << sum << endl;    }}