1055. Combinations

Time limit: 1.0 second
Memory limit: 64 MB

As you have known MMM corporation lab researches the matter of haricot proportions in soup For every day. The ladle is placed down into the soup pan. This ladle holds exactly M haricot seeds of N got into the pan. All the seeds are of different size.

Experimenters calculate the quantity of possible methods to proportion M seeds in the pan with the formula: C = N! / (M! · (N − M)!). The main feature of these experiments is the quantity of different prime divisors of number C.

Lest money would be spent for programmer, MMM corporation board decided to make necessary estimating during the ICPC quarterfinal in Rybinsk. Thus, your aim is to find this quantity.

Input

The only line contains integers N and M that are the number of haricot seeds in the pan and the capacity of the ladle (1 ≤ M < N ≤ 50000).

Output

Output the quantity of different prime divisors of number C.

Sample

input	output
5 3	2

Notes

In the example C = 5! / (3! · 2!) = 120 / (6 · 2) = 10 = 2 · 5.

https://acm.timus.ru/problem.aspx?space=1&num=1055

大意

输入n，m。求出C^m_n中不同质因数的个数

思路

不能算出来，C最大50000！。

map统计质因数，先统计m!,在统计n！，最后统计m-n!

代码

#include <bits/stdc++.h>

using namespace std;

map<int,int>mp;

int main(){

    int m,n;

    cin>>m>>n;

    for(int i=1;i<=m;i++){

        int num=i;

        for(int j=2;j*j<=i&&num!=1;j++){

            while(num%j==0){

                num/=j;

                mp[j]++;

            }

        }

        if(num!=1){

            mp[num]++;

        }

    }

    for(int i=1;i<=n;i++){

        int num=i;

        for(int j=2;j*j<=i&&num!=1;j++){

            while(num%j==0){

                num/=j;

                mp[j]--;

            }

        }

        if(num!=1){

            mp[num]--;

        }

    }

    for(int i=1;i<=m-n;i++){

        int num=i;

        for(int j=2;j*j<=i&&num!=1;j++){

            while(num%j==0){

                num/=j;

                mp[j]--;

            }

        }

        if(num!=1){

            mp[num]--;

        }

    }

    int ans=0;

    for(auto t:mp){

        if(t.second!=0){

            ans++;

        }

    }

    cout<<ans<<endl;

}

巴特西

1055. Combinations