2661-despojados

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "0.5" id: 2661 name: "Despojados" slug: "despojados" timelimit: 1.0 memlimit: 1024 difficultyLevelId: D author: "Maratona de Programação da SBC – 2017" origin: "Beecrowd" description: 'Encontre o número de divisores de N que são formados por produtos de números primos distintos.' editorial: | Um número despojado é um produto de dois ou mais primos distintos. Queremos o número de divisores despojados de N. Seja k o número de fatores primos distintos de N. Qualquer produto de um subconjunto de tamanho >= 2 desses k primos gera um número despojado que obrigatoriamente é divisor de N. Isso é equivalente ao número de subconjuntos de um conjunto de tamanho k, excluindo o subconjunto vazio (tamanho 0) e os subconjuntos de tamanho 1. Portanto, a resposta é 2^k - 1 - k. Para encontrar k, basta fatorar N. Como N <= 10^12, podemos iterar dividindo N por todos os números ímpares (e o 2) até a raiz quadrada de N, que é 10^6. A complexidade é O(sqrt(N)), o que resolve em milésimos de segundo. successmsg: 'Incrível sacada matemática! Usar combinatória básica ($2^k - k - 1$) aliada à fatoração provou o seu domínio.' timeComplexity: O(\sqrt{N}) skills: - math-computing - prime-numbers statements: - id: a-despojados testScenarioLevel: A thematicSkills: - skill: math-computing points: 2 testScenarios: - id: a-performance name: Carga N Gigante description: "Valores de N que são primos próximos a 10^12." helpTip: "Você iterou apenas até a raiz quadrada de N? O(N) é inaceitável aqui." level: A testType: PERFORMANCE skills: - skill: prime-numbers points: 1 - id: b-fuzzing name: Fuzzing description: "Casos variados de N gerados com permutações de primos." helpTip: "Você validou o estado k quando a divisão consome a maior parte mas deixa sobrar 1 primo gigante no N restante?" level: B testType: TDD skills: - skill: prime-numbers points: 1 - id: c-edge name: Menos que Dois Primos description: "N que não pode ter divisores despojados." helpTip: "Seu programa lida com N=1, N=Primo ou N=Primo Quadrado onde a resposta é 0?" level: C testType: TDD skills: - skill: math-computing points: 1 - id: d-sample name: Exemplo do Enunciado description: "Exemplo base do problema." helpTip: "Passe o exemplo básico." level: D testType: TDD skills: - skill: basic-io points: 1 solutions: - id: a-otima-basica name: Combinatória O(sqrt(N)) description: Encontra fatores e calcula combinatória em tempo raiz. level: A implementations: - language: cpp paradigm: Imperative main: despojados.cpp filenames: - despojados.cpp - language: py paradigm: Imperative main: despojados.py filenames: - despojados.py - language: java paradigm: OO main: Despojados filenames: - Despojados.java authorSlugProblem: Unknown defaultStatement: a-despojados