Quase primo - F2P2 - OBI 2016

primo.cpp

// Quase primo - F2P2 - OBI 2016
// Carlos Vinícius
// Complexidade: O(f(N,K))

// obs* f(a,b) é a quantidade de formas de escolher
// até K primos cujo produto não supera N

#include <bits/stdc++.h>

using namespace std;
 
#define MAXK 45
 
int n, k, prime[MAXK];
 
// Função recursiva que gera todos os subconjuntos dos primos da entrada
// idx = índice do primo que estamos analizando no momento;
// prod = produto dos elementos do subconjunto atual;
// qtd = quantidade de elementos no subconjunto atual
int solve(int idx = 0, int prod = 1, int qtd = 0){
	
   	// Se já passei por todos os elementos...
    	if(idx == k){
	    
       		// n/prod é a quantidade de múltiplos menores ou iguais a n do produto acumulado
        	int ret = n/prod;
 
        	// Se a quantidade de elementos for ímpar, a quantidade de múltiplos será retirada da resposta
        	if(qtd%2 == 1){
           		ret = -ret;
        	}
 
        	// Retorno o resultado
        	return ret;
    	}
 
    	// O elemento da posição idx pode ou não entrar no subconjunto;
 
    	// Primeiramente, não insiro o elemento atual no subconjunto
    	int ret = solve(idx + 1, prod, qtd);
 
    	// Agora, considero a possibilidade de inseri-lo. Observe que se o produto passar de N, não é necessário continuar.
    	if(prod*1LL*prime[idx] <= n){
        	ret += solve(idx + 1, prod*prime[idx], qtd + 1);
   	}
 
    	// Retorno o resultado
    	return ret;
}
 
int main(){
   	 // leio N e a quantidade de primos
  	  cin >> n >> k;
 
   	 // leio os primos
   	 for(int i = 0; i < k; i++) cin >> prime[i];
 
    	// e calculo o resultado recursivamente
   	 cout << solve() << "\n";
 
    	// por fim, retorno zero
    	return 0;
}