Dadas las consultas Q. Cada consulta contiene un entero positivo n . La tarea es generar la suma de la suma de los dígitos impares contenidos en todos los divisores de n.
Ejemplos:
Entrada: Q = 2, n1 = 10, n2 = 36
Salida: 7 18
Para Consulta 1,
los divisores de 10 son 1, 2, 5, 10.
La suma de los dígitos impares en 1 es 1, en 2 es 0, en 5 es 5 , en 10 es 1.
Entonces, la suma se convirtió en 7.
Para la consulta 2,
los divisores de 36 son 1, 2, 3, 4, 6, 9, 12, 18, 36.
La suma de los dígitos impares en 1 es 1, en 2 es 0, en 3 es 3, en 4 es 0,
en 6 es 0, en 9 es 9, en 12 es 1, en 18 es 1, en 36 es 3.
Entonces, la suma se convirtió en 18.
La idea es precalcular la suma de dígitos impares de todos los números. Además, podemos usar la suma de los dígitos impares del número anterior para calcular la suma de los dígitos impares del número actual.
Por ejemplo, para calcular la suma del dígito del número impar de «123», podemos usar la suma del dígito del número impar de «12» y «3». Por lo tanto, la suma de los dígitos impares de “123” = la suma de los dígitos impares de “12” + sumar el último dígito si es impar (es decir, 3).
Ahora, para encontrar la suma de la suma de dígitos impares de los factores, podemos usar el fenómeno de salto de la criba de Eratóstenes . Entonces, para todos los factores posibles, agregue su contribución a sus múltiplos.
Por ejemplo, para 1 como factor, agregue 1 (porque 1 tiene solo 1 dígito impar) a todos sus múltiplos.
para 2 como factor, sume 0 a todos los múltiplos de 2, es decir, 2, 4, 8,…
para 3 como factor, sume 1 a todos los múltiplos de 3, es decir, 3, 6, 9,…
A continuación se muestra la implementación de este enfoque:
C++
// CPP Program to answer queries on sum
// of sum of odd number digits of all
// the factors of a number
#include <bits/stdc++.h>
using namespace std;
#define N 1000005
// finding sum of odd digit number in each integer.
void sumOddDigit(int digitSum[])
{
// for each number
for (int i = 1; i < N; i++) {
// using previous number sum, finding
// the current number num of odd digit
// also, adding last digit if it is odd.
digitSum[i] = digitSum[i / 10] + (i & 1) * (i % 10);
}
}
// finding sum of sum of odd digit of all
// the factors of a number.
void sumFactor(int digitSum[], int factorDigitSum[])
{
// for each possible factor
for (int i = 1; i < N; i++) {
for (int j = i; j < N; j += i) {
// adding the contribution.
factorDigitSum[j] += digitSum[i];
}
}
}
// Wrapper function
void wrapper(int q, int n[])
{
int digitSum[N];
int factorDigitSum[N];
sumOddDigit(digitSum);
sumFactor(digitSum, factorDigitSum);
for (int i = 0; i < q; i++)
cout << factorDigitSum[n[i]] << " ";
}
// Driver Program
int main()
{
int q = 2;
int n[] = { 10, 36 };
wrapper(q, n);
return 0;
}
Java
// Java Program to answer queries
// on sum of sum of odd number
// digits of all the factors of
// a number
class GFG
{
static int N = 1000005;
// finding sum of odd digit
// number in each integer.
static void sumOddDigit(int digitSum[])
{
// for each number
for (int i = 1; i < N; i++)
{
// using previous number sum,
// finding the current number
// num of odd digit also,
// adding last digit if it
// is odd.
digitSum[i] = digitSum[i / 10] +
(i & 1) * (i % 10);
}
}
// finding sum of sum of odd digit
// of all the factors of a number.
static void sumFactor(int digitSum[],
int factorDigitSum[])
{
// for each possible factor
for (int i = 1; i < N; i++)
{
for (int j = i; j < N; j += i)
{
// adding the contribution.
factorDigitSum[j] += digitSum[i];
}
}
}
// Wrapper function
static void wrapper(int q, int n[])
{
int digitSum[] = new int[N];
int factorDigitSum[] = new int[N];
sumOddDigit(digitSum);
sumFactor(digitSum, factorDigitSum);
for (int i = 0; i < q; i++)
System.out.print(factorDigitSum[n[i]]
+ " ");
}
// Driver Code
public static void main(String args[])
{
int q = 2;
int n[] = new int[]{10, 36};
wrapper(q, n);
}
}
// This code is contributed by Sam007
Python3
# Python Program to answer queries
# on sum of sum of odd number
# digits of all the factors
# of a number
N = 100
digitSum = [0] * N
factorDigitSum = [0] * N
# finding sum of odd digit
# number in each integer.
def sumOddDigit() :
global N,digitSum,factorDigitSum
# for each number
for i in range(1, N) :
# using previous number
# sum, finding the current
# number num of odd digit
# also, adding last digit
# if it is odd.
digitSum[i] = (digitSum[int(i / 10)]
+ int(i & 1) * (i % 10))
# finding sum of sum of
# odd digit of all the
# factors of a number.
def sumFactor() :
global N,digitSum,factorDigitSum
j = 0
# for each possible factor
for i in range(1, N) :
j = i
while (j < N) :
# adding the contribution.
factorDigitSum[j] = (factorDigitSum[j]
+ digitSum[i])
j = j + i
# Wrapper def
def wrapper(q, n) :
global N,digitSum,factorDigitSum
for i in range(0, N) :
digitSum[i] = 0
factorDigitSum[i] = 0
sumOddDigit()
sumFactor()
for i in range(0, q) :
print ("{} ".
format(factorDigitSum[n[i]]), end = "")
# Driver Code
q = 2
n = [ 10, 36 ]
wrapper(q, n)
# This code is contributed by
# Manish Shaw(manishshaw1)
C#
// C# Program to answer queries on sum
// of sum of odd number digits of all
// the factors of a number
using System;
class GFG {
static int N = 1000005;
// finding sum of odd digit number in
// each integer.
static void sumOddDigit(int []digitSum)
{
// for each number
for (int i = 1; i < N; i++) {
// using previous number sum,
// finding the current number
// num of odd digit also,
// adding last digit if it
// is odd.
digitSum[i] = digitSum[i / 10]
+ (i & 1) * (i % 10);
}
}
// finding sum of sum of odd digit
// of all the factors of a number.
static void sumFactor(int []digitSum,
int []factorDigitSum)
{
// for each possible factor
for (int i = 1; i < N; i++) {
for (int j = i; j < N; j += i)
{
// adding the contribution.
factorDigitSum[j] += digitSum[i];
}
}
}
// Wrapper function
static void wrapper(int q, int []n)
{
int []digitSum = new int[N];
int []factorDigitSum = new int[N];
sumOddDigit(digitSum);
sumFactor(digitSum, factorDigitSum);
for (int i = 0; i < q; i++)
Console.Write(factorDigitSum[n[i]]
+ " ");
}
// Driver code
public static void Main()
{
int q = 2;
int []n = new int[]{ 10, 36 };
wrapper(q, n);
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP Program to answer queries
// on sum of sum of odd number
// digits of all the factors
// of a number
$N = 1000005;
// finding sum of odd digit
// number in each integer.
function sumOddDigit(&$digitSum)
{
global $N;
// for each number
for ($i = 1; $i < $N; $i++)
{
// using previous number
// sum, finding the current
// number num of odd digit
// also, adding last digit
// if it is odd.
$digitSum[$i] = $digitSum[intval($i / 10)] +
intval($i & 1) *
($i % 10);
}
}
// finding sum of sum of
// odd digit of all the
// factors of a number.
function sumFactor($digitSum,
&$factorDigitSum)
{
global $N;
// for each possible factor
for ($i = 1; $i < $N; $i++)
{
for ($j = $i; $j < $N; $j += $i)
{
// adding the contribution.
$factorDigitSum[$j] += $digitSum[$i];
}
}
}
// Wrapper function
function wrapper($q, $n)
{
global $N;
$digitSum = array();
$factorDigitSum = array();
for ($i = 0; $i < $N; $i++)
{
$digitSum[$i] = 0;
$factorDigitSum[$i] = 0;
}
sumOddDigit($digitSum);
sumFactor($digitSum, $factorDigitSum);
for ($i = 0; $i < $q; $i++)
echo ($factorDigitSum[$n[$i]]. " ");
}
// Driver Code
$q = 2;
$n = array( 10, 36 );
wrapper($q, $n);
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>
// Javascript Program to answer queries on sum
// of sum of odd number digits of all
// the factors of a number
var N = 1000005;
// finding sum of odd digit number in each integer.
function sumOddDigit(digitSum)
{
// for each number
for (var i = 1; i < N; i++) {
// using previous number sum, finding
// the current number num of odd digit
// also, adding last digit if it is odd.
digitSum[i] = digitSum[parseInt(i / 10)] + (i & 1) * (i % 10);
}
}
// finding sum of sum of odd digit of all
// the factors of a number.
function sumFactor(digitSum, factorDigitSum)
{
// for each possible factor
for (var i = 1; i < N; i++) {
for (var j = i; j < N; j += i) {
// adding the contribution.
factorDigitSum[j] += digitSum[i];
}
}
}
// Wrapper function
function wrapper(q, n)
{
var digitSum = Array(N).fill(0);
var factorDigitSum = Array(N).fill(0);
sumOddDigit(digitSum);
sumFactor(digitSum, factorDigitSum);
for (var i = 0; i < q; i++)
document.write( factorDigitSum[n[i]] + " ");
}
// Driver Program
var q = 2;
var n = [ 10, 36 ];
wrapper(q, n);
// This code is contributed by noob2000.
</script>
Producción :
7 18