e-olymp 8671. Представимые суммой квадратов

15/12/2019 by Алина Зозуля

Задача

Найдите все числа от $1$ до $n$, представимые в виде суммы двух квадратов различных натуральных чисел.

Входные данные

Одно натуральное число $n$ $( n \leqslant 10000)$.

Выходные данные

Выведите в одной строке в возрастающем порядке все числа от $1$ до $n$, представимые в виде суммы двух квадратов различных натуральных чисел.

Тесты

№	Входные данные	Выходные данные
1	5	5
2	10	5 10
3	13	5 10 13
4	20	5 10 13 17 20
5	30	5 10 13 17 20 25 26 29

Код программы

#include <iostream>
#include <cmath>
using namespace std;
bool check(int n)
{
    
    for (int i = 1; i * i < n; i++) // перебор всех i
    {   
        double j = sqrt (n - i * i);
        if ((j == floor(j)) and (j != i)) // проверка j целое или дробное 
            {
                return true; // комбинация найдена - возвращаем true
            }
    } 
    return false; // комбинация не найдена - возвращаем false
}
int main() {
    int n;
    cin >> n; // считываем число, до которого будем искать
    for (int k = 5; k <= n; k++) // проверка для каждого k
        if (check(k))
            cout << k << " ";
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

bool check(int n)

{

for (int i = 1; i * i < n; i++) // перебор всех i

{

double j = sqrt (n - i * i);

if ((j == floor(j)) and (j != i)) // проверка j целое или дробное

{

return true; // комбинация найдена - возвращаем true

}

return false; // комбинация не найдена - возвращаем false

}

int main() {

int n;

cin >> n; // считываем число, до которого будем искать

for (int k = 5; k <= n; k++) // проверка для каждого k

if (check(k))

cout << k << " ";

return 0;

}

Решение

Для решения задачи создадим функцию check(), которая будет возвращать $true$, если число можно представить в виде суммы двух квадратов или же $false$, если нельзя. В функции перебираем всевозможные варианты $i$ и считаем $j$ для каждого $i$ по формуле $j=\sqrt{n-i^2}$, до тех пор пока не найдем целое (не равное $i$ ) $j$ или же не переберем все $i$. Просматриваем до $ i \cdot i < n $, потому что сумма двух квадратов не может превышать заданного числа. Формулу получили выразив $j$ из исходной формулы $(i^2+j^2=n)$.

Ссылки

Условие задачи на e-olymp

Код программы на ideone

Related Images:

e-olymp 519. Сумма квадратов

16/11/2017 by Иван Василевский

Как лучше кодировать квадрат?

Условие задачи
Найти сумму квадратов двух чисел.

Входные данные
Два целых числа [latex]a[/latex] и [latex]b[/latex]. Числа не превышают [latex]10^9[/latex] по абсолютной величине.

Выходные данные
Выведите одно целое число [latex]a^2 + b^2.[/latex] Continue reading →

Related Images:

А136д

09/11/2014 by Швандт Максим Альбертович

Задача: Даны натуральное число [latex]n[/latex], действительные числа [latex] a_{1},\ldots,a_{n} [/latex].

Вычислить:

[latex] a^{2}{1}+\ldots+a^{2}{n} [/latex];

Тесты:

n	a	result
0	1, 2	error: out of range
2	5, 8	89
3	6, 13, 4	221
4	1, 2	error: incomplete input
7	2, 4, 8, 16, 32, 64, 128	21844

Код программы:

#include <stdio.h>


int main() {

   // рабочие переменные
   int i, n;
   double r;
   
   // ввод количества элементов суммы
   if( scanf("%d", &n) <= 0 )
   {
      printf("error: missing n\n" );
      return 0;
   }
   
   // проверка количества элементов суммы
   if( n <= 0 )
   {
      printf("error: out of range: n=%d\n", n);
      return 0;
   }
   
   // ввод чисел " а "
   for( i = 0, r = 0; i < n; i++ )
   {
      double a = 0;
      
      if( scanf("%lf", &a ) <= 0 )
      {
         printf("error: incomplete input of value #%d\n", i);
     return 0;
      }  

      // основный цикл вычисления
      r += a * a; 
   }
   
   // вывод результата
   printf("result: %lf\n", r );
   
   return 0;
}

#include <stdio.h>

int main() {

// рабочие переменные

int i, n;

double r;

// ввод количества элементов суммы

if( scanf("%d", &n) <= 0 )

{

printf("error: missing n\n" );

return 0;

}

// проверка количества элементов суммы

if( n <= 0 )

{

printf("error: out of range: n=%d\n", n);

return 0;

}

// ввод чисел " а "

for( i = 0, r = 0; i < n; i++ )

{

double a = 0;

if( scanf("%lf", &a ) <= 0 )

{

printf("error: incomplete input of value #%d\n", i);

return 0;

}

// основный цикл вычисления

r += a * a;

}

// вывод результата

printf("result: %lf\n", r );

return 0;

}

Код прогрммы на языке Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class CountApp
{
   public static Integer scanInteger( Scanner in )
   {
       return ( ( in.hasNextInt() ) ? in.nextInt() : null );
   }

   public static Double scanDouble( Scanner in )
   {
       return ( ( in.hasNextDouble() ) ? in.nextDouble() : null );
   }
   
   
   public static void main( String[] args )
   {

      // рабочие переменные
      int i, n;
      double r;
      
      // ввод количества элементов суммы
      Scanner in = new Scanner(System.in);
      
      n = scanInteger( in );
      
      if( n <= 0 )
      {
          System.out.printf("error: missing n\n" );
         return;
      }
      
      // проверка количества элементов суммы
      if( n <= 0 )
      {
          System.out.printf("error: out of range: n=%d\n", n);
         return;
      }
      
      // ввод чисел " а "
      for( i = 0, r = 0; i < n; i++ )
      {
         double a = 0;
         
         a = scanDouble( in );
         
         if( a <= 0 )
         {
             System.out.printf("error: incomplete input of value #%d\n", i);
        return;
         }  
      
         // основный цикл вычисления
         r += a * a; 
      }
      
      in.close(); 
      
      // вывод результата
       System.out.printf("result: %f\n", r );
   }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class CountApp

{

public static Integer scanInteger( Scanner in )

{

return ( ( in.hasNextInt() ) ? in.nextInt() : null );

}

public static Double scanDouble( Scanner in )

{

return ( ( in.hasNextDouble() ) ? in.nextDouble() : null );

}

public static void main( String[] args )

{

// рабочие переменные

int i, n;

double r;

// ввод количества элементов суммы

Scanner in = new Scanner(System.in);

n = scanInteger( in );

if( n <= 0 )

{

System.out.printf("error: missing n\n" );

return;

}

// проверка количества элементов суммы

if( n <= 0 )

{

System.out.printf("error: out of range: n=%d\n", n);

return;

}

// ввод чисел " а "

for( i = 0, r = 0; i < n; i++ )

{

double a = 0;

a = scanDouble( in );

if( a <= 0 )

{

System.out.printf("error: incomplete input of value #%d\n", i);

return;

}

// основный цикл вычисления

r += a * a;

}

in.close();

// вывод результата

System.out.printf("result: %f\n", r );

}

Ссылка: https://ideone.com/x0q7r4

План программы:

Назначение рабочих переменных
Ввод количества элементов суммы
Проверка ввода n
Ввод чисел » а «
Цикл вычисления
Вывод результата

Программе задаётся число n элементов суммы и сами элементы. При получении этих данных программа вычисляет сумму. Если количество элементов меньше или равно 0 , программа сообщает о невозможности выполнения операции по суммированию. Входные данные используются по мере ввода, они нигде не сохраняются, т.к. используются единожды для накопления общего результата.

Ссылка на ideone.com: http://ideone.com/dxXr0Q