fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define lli long long int
  4. lli sum_prime_fac[1000001];
  5. void PSIEVE(){
  6.     sum_prime_fac[1000001] = {0};
  7.     for(int i=2;i<=1000000;i++){
  8.             if(!sum_prime_fac[i]){
  9.                     for(int j=i;j<=1000000;j+=i)
  10.                         sum_prime_fac[j]+=i;
  11.             }
  12.     }
  13. }
  14.  
  15. lli inverse(lli a,lli b,lli p){
  16.     lli an=1;
  17.     while(b){
  18.         if(b%2)
  19.             an=(an*1ll*a)%p;
  20.         a=(a*1ll*a)%p;
  21.         b/=2;
  22.     }
  23.     return an;
  24. }
  25.  
  26. int getSubsets(int k, int n, vector<int> arr) {
  27.     PSIEVE();
  28.     long int mod = 1000000007;
  29.     int sum=0,i,j;
  30.     for(i=0;i<arr.size();i++)
  31.         sum= (sum%1000000 + sum_prime_fac[arr[i]]%1000000)%1000000;
  32.     lli fac1=1,fac2=1,fac3=1;
  33.     for(int i=1;i<=sum+k-1;i++)
  34.         fac1 = (fac1*1LL*i)%mod;
  35.     for(int i=1;i<=sum;i++)
  36.         fac2 = (fac2*1LL*i)%mod;
  37.     for(int i=1;i<k;i++)
  38.         fac3 = (fac3*1LL*i)%mod;
  39.     lli fac2in = inverse(fac2,mod-2,mod);
  40.     lli fac3in = inverse(fac3,mod-2,mod);
  41.     fac1 = ((fac1%mod)*(fac2in%mod))%mod;
  42.     fac1 = ((fac1%mod)*(fac3in%mod))%mod;
  43.     return(fac1);
  44. }
  45. using namespace std;
  46.  
  47. int main() {
  48. 	vector<int>vec({1,2,6});
  49. 	int n=3;
  50. 	int k=3;
  51. 	cout<<getSubsets(3,3,vec);
  52. 	return 0;
  53. }
Success #stdin #stdout 0.02s 11368KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
36
https://ideone.com/ADG9wu
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!