Artigos

4.3: A Função de Mobius e a Fórmula de Inversão de Mobius


Começamos definindo a função Mobius que investiga inteiros em termos de sua decomposição primária. Em seguida, determinamos a fórmula de inversão de Mobius que determina os valores da função a (f ) em um dado inteiro em termos de sua função somativa.

( mu (n) = left { begin {array} {lcr} 1 mbox {if} n = 1; (-1) ^ t mbox {if} } n = p_1p_2 ... p_t mbox {onde} p_i mbox {são primos distintos}; 0 mbox {caso contrário}. end {array} certo .)

Observe que se (n ) é divisível por uma potência de um primo maior que um, então ( mu (n) = 0 ).

Em conexão com a definição acima, temos o seguinte

Diz-se que um inteiro (n ) é livre de quadrados, se nenhum quadrado o divide, ou seja, se não existe um inteiro (k ) tal que (k ^ 2 mid n ).

É imediato (prove como exercício) que a fatoração de números primos de um inteiro livre de quadrados contém apenas primos distintos.

Observe que ( mu (1) = 1 ), ( mu (2) = - 1 ), ( mu (3) = - 1 ) e ( mu (4) = 0 )

Agora provamos que ( mu (n) ) é uma função multiplicativa.

A função Mobius ( mu (n) ) é multiplicativa.

Sejam (m ) e (n ) dois inteiros relativamente primos. Temos que provar que [ mu (mn) = mu (m) mu (n). ] Se (m = n = 1 ), então a igualdade se mantém. Além disso, sem perda de generalidade, se (m = 1 ), então a igualdade também é óbvia. Agora suponha que (m ) ou (n ) seja divisível por uma potência do primo maior que 1, então [ mu (mn) = 0 = mu (m) mu (n). ] O que resta provar que se (m ) e (n ) são inteiros sem quadrados digamos (m = p_1p_2 ... p_s ) onde (p_1, p_2, ..., p_s ) são primos distintos e (n = q_1q_2 ... q_t ) onde (q_1, q_2, ..., q_t ). Uma vez que ((m, n) = 1 ), então não há primos comuns na decomposição primária entre (m ) e (n ). Assim, [ mu (m) = (- 1) ^ s, mu (n) = (- 1) ^ t mbox {e} mu (mn) = (- 1) ^ {s + t }. ]

No teorema a seguir, provamos que a função somativa da função Mobius assume apenas os valores (0 ) ou (1 ).

Seja (F (n) = sum_ {d mid n} mu (d) ), então (F (n) ) satisfaz [F (n) = left { begin {array} {lcr} 1 mbox {if} n = 1; 0 mbox {if} n> 1. end {array} right. ]

Para (n = 1 ), temos (F (1) = mu (1) = 1 ). Vamos agora encontrar ( mu (p ^ k) ) para qualquer inteiro (k> 0 ). Observe que [F (p ^ k) = mu (1) + mu (p) + ... + mu (p ^ k) = 1 + (- 1) +0 + ... + 0 = 0 ] Assim, pelo Teorema 36, ​​para qualquer inteiro (n = p_1 ^ {a_1} p_2 ^ {a_2} ... p_t ^ {a_t}> 1 ) temos, [F (n) = F (p_1 ^ {a_1}) F (p_2 ^ {a_2}) ... F (p_t ^ {a_t}) = 0 ]

Agora definimos a fórmula de inversão de Mobius. A fórmula de inversão de Mobius expressa os valores de (f ) em termos de sua função somatória de (f ).

Suponha que (f ) seja uma função aritmética e suponha que (F ) seja sua função somativa, então para todos os inteiros positivos (n ) temos [f (n) = sum_ {d mid n } mu (d) F (n / d). ]

Temos [ begin {alinhados} sum_ {d mid n} mu (d) F (n / d) & = & sum_ {d mid n} mu (d) sum_ {e mid (n / d)} f (e) & = & sum_ {d mid n} sum_ {e mid (n / d)} mu (d) f (e) & = & sum_ {e mid n} sum_ {d mid (n / e)} mu (d) f (e) & = & sum_ {e mid n} f (e) sum_ {d mid (n / d)} mu (d) end {alinhado} ] Observe que ( sum_ {d mid (n / e)} mu (d) = 0 ) a menos que (n / e = 1 ) e, portanto, (e = n ). Conseqüentemente, obtemos [ sum_ {e mid n} f (e) sum_ {d mid (n / d)} mu (d) = f (n) .1 = f (n). ]

Um bom exemplo de uma fórmula de inversão de Mobius seria a inversão de ( sigma (n) ) e ( tau (n) ). Essas duas funções são as funções somativas de (f (n) = n ) e (f (n) = 1 ) respectivamente. Assim, obtemos [n = sum_ {d mid n} mu (n / d) sigma (d) ] e [1 = sum_ {d mid n} mu (n / d) tau (d). ]

Exercícios

  1. Encontre ( mu (12) ), ( mu (10!) ) E ( mu (105) ).
  2. Encontre o valor de ( mu (n) ) para cada inteiro (n ) com (100 leq n leq 110 ).
  3. Use a fórmula de inversão de Mobius e a identidade (n = sum_ {d mid n} phi (n / d) ) para mostrar que ( phi (p ^ t) = p ^ tp ^ {t-1 } ) onde (p ) é um primo e (t ) é um número inteiro positivo.

Fórmulas de inversão de Möbius para fluxos de semigrupos aritméticos ☆

Nós definimos um operador do tipo convolução que transforma funções em um espaço X via funções em um semigrupo aritmético S, quando há uma ação ou fluxo de S em X. Este operador inclui as conhecidas transformadas clássicas de Möbius e fórmulas de inversão associadas como casos especiais. É definido em um contexto suficientemente geral para enfatizar os aspectos universais e funcionais da inversão aritmética de Möbius. Damos condições analíticas gerais que garantem a existência da transformada e a validade das correspondentes fórmulas de inversão, em termos de operadores em determinados espaços de funções. São estudados vários exemplos que ilustram as vantagens do ponto de vista convolucional para a obtenção de novas fórmulas de inversão.


Fórmulas de inversão de Möbius relacionadas às expansões de Fourier de polinômios bidimensionais de Apostol-Bernoulli

Os polinômios bidimensionais (2D) de Apostol – Bernoulli e Apostol – Euler são definidos por meio das funções geradoras t e x t + y t m λ e t - 1 = ∑ n = 0 ∞ B n (x, y λ) t n n! , 2 e x t + y t m λ e t + 1 = ∑ n = 0 ∞ E n (x, y λ) t n n! . Os polinômios Apostol – Bernoulli e Apostol – Euler são essencialmente os mesmos que famílias polinomiais parametrizadas, portanto, podemos nos restringir ao último.

Os coeficientes de Fourier de x ↦ λ x B n (x, y λ) em [0, 1) satisfazem uma fórmula de transformação aritmética-dinâmica que torna a série de Fourier passível de uma técnica de inversão de Möbius generalizada. Isso produz algumas identidades de soma aritmética interessantes, entre elas versões parametrizadas da seguinte fórmula clássica de Davenport: ∑ k = 1 ∞ μ (k) k = - sin ⁡ (2 π x) π (x ∈ R ), onde μ (n) é a função de Möbius e denota a parte fracionária de x. A fórmula de Davenport & # x27s é o caso limite α = 0 de - 4 π 4 π 2 - α 2 sin ⁡ (2 π x) = ∑ k = 1 ∞ μ (k) k ⋅ sin ⁡ (α k ( - 1 2)) 2 sin ⁡ (α 2 k), que é válido para - π & lt α ≤ π.


Na função Möbius

A função Möbius é bastante útil, especialmente ao lidar com funções multiplicativas. Mas, antes de tudo, algumas definições são necessárias.

Definição 1: Seja ( omega (n) ) o número de divisores primos distintos de (n ).

Definição 2: A função Möbius, ( mu (n) ) é definida como ((- 1) ^ < omega (n)> ) se (n ) for livre de quadrados e (0 ) caso contrário . (Um número (n ) é livre de quadrados se não houver primo (p ) tal que (p ^ 2 ) divida (n ).)

Pode ser uma boa ideia calcular o seguinte: ( omega (n) ) e ( mu (n) ) para (n = 64, 12, 17, 1 ) para ter uma ideia do que & # 8217s acontecendo.

Uma função Möbius é uma função aritmética, ou seja, uma função de ( mathbb) para ( mathbb). Você consegue pensar em outras funções aritméticas?

Definição 3: Se (f (n) ) é uma função aritmética não idêntica a zero, de modo que (f (m) f (n) = f (mn) ) para cada par de inteiros positivos (m, n ) satisfazendo ((m, n) = 1 ), então (f (n) ) é multiplicativo.

Prova: Cabe ao leitor fornecer a prova.

Antes de pularmos para a prova, sejamos claros na notação. Para (n = 12 ), ( displaystyle sum_ f (d) = f (1) + f (2) + f (3) + f (4) + f (6) + f (12) ) ou seja, a soma dos divisores de (n ).

(Observe que tal (m_1, m_2 ) existe. Pegue (m_1 = 1, m_2 = n )).

Agora pegue (d em A ). Então (1 cdot d ) divide (1 cdot n ) o que significa que (d em B ) e assim (A subconjunto B ).

Agora pegue (s em B ). Portanto, (s ) tem a forma (d_1d_2 ) onde (d_1 | m_1 ) e (d_2 | m_2 ) tal que ((m_1, m_2) = 1 ) com seu produto (n ). Portanto, (s ) divide (m ) e, portanto, (B subconjunto A ). Destes, inferimos que (A = B ).

Agora, suponha que ((m, n) = 1 ). Então ( displaystyle F (mn) = sum_ f (d) = sum_f (d_1d_2) = sum_soma_ f (d_1d_2) )

Agora, com este teorema em mãos, vamos provar mais alguns teoremas.

Prova: O caso (n = 1 ) é trivial.

Como ( mu (n) ) é multiplicativo, também é ( displaystyle F (n) = sum_ lama)). Agora, vamos lembrar que (n & gt1 ) pode ser escrito como um produto de primos, digamos ( displaystyle n = p_i ^ dots p_k ^). Então, podemos escrever (F (n) = F (p_1 ^) pontos F (p_k ^)).

Como (a_i ge 1 ), (F (p_i ^) = 0 ) (usando a definição de ( mu ).) Isso significa (F (n) = 0 ). A conclusão desejada agora segue desta discussão.

Antes de avançarmos para um teorema que mostra uma conexão entre a função de Euler & # 8217s ( varphi - ) e a função de Möbius, vamos declarar um teorema realmente importante, também conhecido como fórmula de inversão de Möbius.

Prova: Daremos corpo a essa prova com menos detalhes porque desenvolvemos a maioria das técnicas relacionadas à sua prova.

Observe que ( displaystyle sum_ mu (d) F ( frac))

O leitor pode agora completar a prova? (Dica: Use Teorema 2).

Prova: Para escrever a prova, usamos um lema.

Lema: ( displaystyle sum_ varphi (d) = n ).

Prova do lema: Observe que para (n = 1 ), isso é verdade. Suponha que (n & gt1 ). Então ( displaystyle n = p_1 ^ dots p_k ^) para alguns primos (p_1, dots, p_k ). Como ( varphi (n) ) é multiplicativo, também é ( displaystyle F (n) = sum_ varphi (d) )

Isso significa ( displaystyle F (n) = prod_^ k F (p_i ^) ). Um cálculo rápido revela que (F (p_i ^) = p_i ^) que dá (F (n) = n ).

Agora podemos usar este lema e a fórmula da inversão de Möbius para terminar a prova.

Aqui estão alguns outros problemas sobre funções multiplicativas.

Problema 2: Para cada número inteiro positivo (n ), ( displaystyle mu (n) mu (n + 1) mu (n + 2) mu (n + 3) = 0 ).


Recursos da Web da Wolfram

A ferramenta nº 1 para a criação de demonstrações e qualquer coisa técnica.

Explore qualquer coisa com o primeiro mecanismo de conhecimento computacional.

Explore milhares de aplicativos gratuitos em ciências, matemática, engenharia, tecnologia, negócios, arte, finanças, ciências sociais e muito mais.

Junte-se à iniciativa de modernização do ensino de matemática.

Resolva integrais com Wolfram | Alpha.

Analise os problemas do dever de casa passo a passo, do começo ao fim. As dicas ajudam você a tentar a próxima etapa por conta própria.

Problemas de prática aleatória ilimitada e respostas com soluções passo a passo integradas. Pratique online ou faça uma folha de estudo para impressão.

Coleção de ferramentas de ensino e aprendizagem criadas por especialistas em educação da Wolfram: livro didático dinâmico, planos de aula, widgets, demonstrações interativas e muito mais.


Subseção 23.4.2 Trazendo a estrutura do grupo

Vamos nos aprofundar na estrutura algébrica por trás da operação ( star ). Lembre-se, (f star g ) é definido por begin(f star g) (n) = sum_f (d) g (e) . end

Essa estrutura é tão bacana porque, na verdade, nos permite generalizar a ideia por trás da função de Moebius!

Teorema 23.4.3

Se (f ) é uma função aritmética e (f (1) neq 0 ), então (f ) tem um inverso no conjunto (A ) sob a operação ( star ). Chamamos isso de inverso (f ^ <-1> ). É dado pela seguinte definição recursiva: begincomeçar f ^ <-1> (1) = frac <1> & amp n = 1 sum_f ^ <-1> (d) f left ( frac direita) = sum_f ^ <-1> (d) f (e) = 0 & amp n & gt1 endfim

Prova

Como em todos os melhores teoremas, não há realmente nada a provar. Sempre podemos obter o próximo valor de (f ^ <-1> (n) ) pelo conhecimento de (f ^ <-1> (d) ) para (d mid n ), e isso é o suficiente para uma prova de indução, uma vez que temos uma fórmula dada para (f ^ <-1> (1) ). (Veja o Exercício 23.5.9)

Corolário 23.4.4

Isso diz exatamente que a função Moebius ( mu ) é ( mu = u ^ <-1> ).

Este é um bom momento para tentar descobrir qual é o inverso de (N ) ou ( phi ) com papel e lápis. Consulte os Exercícios Exercício 23.5.4 e Exercício 23.5.5.

Em geral, também podemos dizer que beginf star f ^ <-1> = I = f ^ <-1> star f end Há outra implicação, mais teórica, também.

Corolário 23.4.5

O subconjunto de (A ) que consiste em todas as funções aritméticas com (f (1) neq 0 ) é na verdade um grupo.


Provando a Fórmula de Inversão de Mobius

Então, nos últimos dias, venho tentando provar a fórmula de Inversão de Mobius:

A melhor maneira de obter uma compreensão intuitiva desta fórmula é escrever algumas equações de forma extensa.

Por exemplo, calculei os valores de para vários n.

Os valores para podem ser facilmente calculados.

É literalmente incrível ver como os sinais nas equações elaboradas correspondem exatamente ao que se obteria ao aplicar a Função Mobius!

Achei que a função Mobius parecia bastante inútil, então foi estimulante ver a conexão entre resolver essas equações e a função Mobius.

Por algum tempo, eu abordei a prova em termos de tentar generalizar minha solução das equações para etc. No entanto, isso não funcionou.

No entanto, ontem comecei a brincar com a própria fórmula para ver o que acontece. Como primeiro passo, comecei a trabalhar com.

Eu reescrevi isso como. Digamos que definamos a função de identidade i (n) = 1, então temos a seguinte equação


Observe que a condição de completude de Rezk, que (s_0: X_0 rightarrow X_1 ) induz uma equivalência no subespaço de equivalências, que é a condição de completude usual na teoria dos espaços Segal, implica a presente condição de completude para o espaço de decomposição.

Aguiar, M., Bergeron, N., Sottile, F .: Álgebras de Hopf combinatórias e relações generalizadas de Dehn-Sommerville. Compos. Matemática. 142(1), 1–30 (2006)

Bergner, J.E., Osorno, A.M., Ozornova, V., Rovelli, M., Scheimbauer, C.I .: Conjuntos 2-Segal e a construção de Waldhausen. Topol. Appl. 235, 445–484 (2018)

Carlier, L .: Incidence bicomodules, Möbius inversion, and a Rota formula for infinito adjunctions. Algebr. Geometr. Topol. 20, 169–213 (2020)

Cartier, P., e Foata, D .: Problèmes combinatoires de commutation et réarrangements. Notas de aula em matemática, No. 85. Springer-Verlag, Berlin-New York, (1969)

Dyckerhoff, T., e Kapranov, M .: Espaços Segal Superiores I. Volume 2244 de Notas de aula em matemática. Springer, (2019)

Feller, M., Garner, R., Kock, J., Proulx, M.U., Weber, M .: Cada espaço 2-Segal é unital. Comum. Contemp. Matemática. 23, 2050055 (2021)

Gálvez-Carrillo, I., Kock, J., Tonks, A .: Groupoids e Faá di Bruno fórmulas para funções de Green em bialgebras de árvores. Adv. Matemática. 254, 79–117 (2018)

Gálvez-Carrillo, I., Kock, J., Tonks, A .: Espaços de decomposição, álgebras de incidência e inversão de Möbius I: teoria básica. Adv. Matemática. 331, 952–1015 (2018)

Gálvez-Carrillo, I., Kock, J., Tonks, A .: Espaços de decomposição, álgebras de incidência e inversão de Möbius II: completude, filtração de comprimento e finitude. Adv. Matemática. 333, 1242–1292 (2018)

Gálvez-Carrillo, I., Kock, J., Tonks, A .: Espaços de decomposição e espécies de restrição. Int. Matemática. Res. Não. 7558–7616, 2020 (2020)

Gálvez-Carrillo, I., Kock, J., e Tonks, A .: Espaços de decomposição em combinatória. Pré-impressão, arXiv: 1612.09225

Illusie, L .: Complexe cotangent et déformations II. Lecture Notes in Mathematics, vol. 283. Springer, Berlin (1972)

Joyal, A., Tierney, M .: Quasi-categorias vs espaços Segal. Contemp. Matemática. 431, 277–326 (2007)

Kock, J .: Categorificação de álgebras de Hopf de árvores enraizadas. Central Eur. J. Math. 11(3), 401–422 (2013)

Kock, J., Weber, M .: Faá di Bruno para óperas e álgebras internas. J. Lond. Matemática. Soc. 99, 919–944 (2019)

Leroux, P .: Les catégories de Möbius. Cahiers de topologie et géométrie différentielle 16, 280–282 (1975)

Penney, M. D .: Espaços Simpliciais, álgebras relaxadas e a condição 2-Segal. Pré-impressão, arxiv: 1710.02742

Rota, G.-C .: Sobre os fundamentos da teoria combinatória I. Teoria das funções de Möbius. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 2, 340–368 (1964)

Schmitt, W.R .: Hopf algebras of combinatorial structure. Pode. J. Math. 45, 412–428 (1993)


4.3: A Função de Mobius e a Fórmula de Inversão de Mobius

Escritório: 234B, Engenharia 1
Telefone: (312) 567-3128
E-mail: kaul [arroba] math.iit.edu

Horário: 15h15, terça e quinta-feira.
Local: 106, Engenharia 1 Prédio.

Horário de atendimento: 13h-14h terça e quinta-feira, visitas e com hora marcada. Perguntas por e-mail também são incentivadas.

O Apostila de informações do curso tem ampla descrição do curso - tópicos, livro-texto, política de avaliação do aluno, bem como outras informações relevantes. Leia atentamente!

Excelente conselho de Doug West sobre como escrever soluções de lição de casa em um curso como este e como escrever soluções de lição de casa para problemas baseados em provas.

Por que temos que aprender provas?
Noções básicas sobre matemática - um guia de estudo
Em uma nota mais abstrata, aqui está uma discussão sobre Linguagem e Gramática da Matemática - que é o que você está começando a aprender em um curso como este.

Excelente conselho para matemáticos, especialmente aqueles que planejam fazer pós-graduação, por Terry Tao, medalhista de 2006 Fields. Leitura obrigatória.

  • Quinta-feira, 23/04 : O dever de casa nº 11 foi carregado. É mais longo do que o normal, mas você tem 12 dias para terminá-lo.
  • Quinta-feira, 9/4 : O exame # 2 foi anunciado.
  • Terça-feira, 24/02 : O exame # 1 foi anunciado.
  • Quinta-feira, 2/12 : Corrigi o Exercício Suplementar nº 11, uma parte do HW nº 3. A solução para este problema corrigido será entregue na quinta-feira, 19/02.
  • Quinta-feira, 2/5 : Comecei a enviar folhetos relacionados ao material abordado em aula na seção de registro da aula abaixo. Nas seções posteriores, também irei fazer upload de exemplos que não foram feitos em sala de aula / livro didático.
  • Quinta-feira, 29/01 : Por favor, tome nota da 'Política importante' declarada na seção Trabalho de casa abaixo.
  • Quinta-feira, 22/01 : Verifique esta página da web regularmente para tarefas de casa, anúncios, etc.
  • Exame # 1 : Quinta-feira, 12 de março. Tópicos: Tudo abordado em aula até e incluindo a palestra de quinta-feira, 26/02. Isso corresponde ao material coberto em HW # 1 a HW # 6.
  • Exame # 2 : Quinta-feira, 23 de abril. Tópicos: Tudo abordado na aula de terça, 03/03 a quinta-feira, 09/04 (incluindo os dois dias). Isso corresponde ao material coberto em HW # 7 a HW # 10.
  • Exame final : Quinta-feira, 14 de maio, das 14h às 16h. Tópicos: todos os tópicos estudados durante o semestre.

Você só precisa enviar soluções para problemas escritos .
No entanto, resolvendo a maioria das problemas sugeridos é fortemente encorajado. Resolver esses problemas irá melhorar sua compreensão do material do curso e prepará-lo melhor para os exames.

    Exercícios Complementares. Este arquivo contém problemas interessantes de fora do livro será atualizado ao longo do semestre.


Qual é a inversão de Möbius?

De acordo com a Wikipedia, a inversão de Möbius afirma que:

Se para cada número inteiro positivo n , então , onde μ (x) é a função Möbius, que é multiplicativa e satisfaz f(1) = 1, f(p) = - 1, f(p k ) = 0 para qualquer número primo p e qualquer inteiro k ≥ 2 . ( É importante notar que você pode pré-calcular todos os valores da função Möbius de 1 a n usando a peneira linear. )

No entanto, a definição por si só não significa muito (a menos que a declaração do problema forneça explicitamente algo como . Nesse caso, bem. ) Existe uma propriedade importante que provavelmente é mais útil do que a definição:

A fim de provar essa propriedade, temos que usar a propriedade transitiva de funções multiplicativas para mostrar que é multiplicativo. Depois disso, podemos ver f(1) = 1 e f(p k ) = 0, o que significa f(x) = ε (x) Agora você pode perguntar: por que essa propriedade é importante? Acho que é melhor mostrar as razões em alguns exemplos básicos abaixo.

Exemplo 1. Descubra o número de pares primos de inteiros (x, y) no intervalo [1, n] .

Solução 1. Observe que a pergunta é o mesmo que perguntar a você o valor de

Agora aplique a inversão de Möbius em [gcd(eu, j)] = 1, temos

Notar que [d|gcd(eu, j)] = [d|eu][d|j] Portanto

Podemos mudar a ordem de somar as coisas, então

Nós sabemos isso . Desse modo

Então, podemos simplesmente fazer um loop de 1 a n para calcular a fórmula. Embora possamos otimizar este loop para usando o lema harmônico, ainda temos que usar a peneira linear para pré-calcular os valores de μ (d) Portanto, a complexidade geral do algoritmo é O(n) .

Exemplo 2. Descubra a soma de gcd(x, y) para cada par de inteiros (x, y) no intervalo [1, n] ( gcd(x, y) significa o maior divisor comum de x e y ).

Solução 2. Semelhante ao anterior, observe que a pergunta é o mesmo que perguntar a você o valor de

Deixar k = gcd(eu, j) Podemos então fazer um loop para k primeiro.

Agora assuma eu = ak, j = bk , e então

Pode-se observar que a última parte da fórmula é a mesma do exemplo 1. Aplicando o mesmo procedimento, temos

De acordo com o lema harmônico, . Portanto, se calcularmos a soma acima com força bruta, a complexidade geral será .

Esta não é, no entanto, a melhor complexidade que podemos alcançar com a inversão de Möbius. Agora deixe eu = kd , e podemos fazer um loop para eu primeiro.

Aplicando a propriedade transitiva de funções multiplicativas, podemos ver que é multiplicativo. Além disso, temos g(p k ) = p k - p k - 1. Se você estudou um pouco sobre a teoria dos números, pode descobrir que g(eu) é na verdade a função totiente de Euler. Independentemente de saber se você sabe sobre a coincidência ou não, g(eu) pode ser pré-calculado com a peneira linear, e , que pode ser simplesmente calculado em O(n) complexidade.

Exemplo 3. Descubra a soma de lcm(x, y) para cada par de inteiros (x, y) no intervalo [1, n] ( lcm(x, y) significa o mínimo múltiplo comum de x e y ).

Solução 3. Bem, devemos estar bem familiarizados com as técnicas agora. Em primeiro lugar, a resposta deve ser

Desde , deixar k = gcd(eu, j) Podemos então fazer um loop para k primeiro.

Agora assuma eu = ak, j = bk , e então

Agora vamos assumir uma = dp, b = dq , então

Agora observe , e nós temos

Agora seguindo o exemplo acima, vamos eu = kd , e então

Notar que também é multiplicativo, e g(p k ) = p k - p k + 1. Podemos pré-calcular os valores de g(eu) por meio da peneira linear, e . A complexidade geral será O(n) .

Exemplo 4. Descubra a soma de lcm(UMA[eu], UMA[j]) para cada par de inteiros (UMA[eu], UMA[j]) com uma matriz UMA de comprimento N ( 1 ≤ eu, jN ), com a restrição de 1 ≤ N ≤ 200, 000 e 1 ≤ UMA[eu] ≤ 1, 000, 000 .

Solução 4. Esta é uma variação comum do exemplo acima. Denotar

Deixar t = dl , então

Agora, semelhante ao exemplo acima é multiplicativo com g(p k ) = p - k - p - k + 1 e, portanto, pode ser calculado com O(V) , Onde V é o intervalo de UMA . A última parte da fórmula também é bastante fácil de descobrir se você controlar o número de elementos igual a v Como cnt(v) , desde

e com o lema harmônico, o cálculo acima pode ser feito em . Portanto, a complexidade geral é .


Assista o vídeo: Funções aritméticas, função de Möbius (Outubro 2021).