Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 오일러의 4제곱 항등

<시간/>

이 문제에서는 두 개의 숫자가 주어지고 오일러의 4제곱 항등식을 사용하여 숫자의 곱을 찾아야 합니다.

오일러의 4제곱 아이덴티티 네제곱의 합을 사용하여 나타낼 수 있는 두 수의 곱을 찾는 방법입니다. 숫자가 4개의 제곱의 합으로 표현될 수 있는 경우의 숫자입니다.

제품 a * b는 다음과 같은 경우 네 제곱의 합으로 나타낼 수 있습니다.

a =x1 2 + x2 2 + x3 2 + x4 2
b =y1 2 + y2 2 + y3 2 + y4 2
a * b =z1 2 + z2 2 + z3 2 + z4 2

문제를 이해하기 위해 예를 들어 보겠습니다.

입력:

a =54 =2*2 + 3*3 + 4*4 + 5*5

b =10 =1*1 + 2*2 + 1*1 + 2*2


출력: 1*1 + 1*1 + 3*3 + 23*23

설명:

a와 b의 곱 =540,

여러 가지로 표현할 수 있는 것입니다. 여기에서 한 가지 해결책을 찾을 수 있습니다.

540 =1*1 + 1*1 + 3*3 + 23*23 =1 + 1 + 9 + 529

해결 방법 -

문제에 대한 간단한 해결책은 시행 방법을 사용하여 문제를 해결하기 위해 4개의 제곱 조합을 각각 시도하는 것입니다. 이를 위해 우리는 각 제곱 값에 대해 하나의 중첩 루프인 중첩 루프를 사용할 것입니다. 그런 다음 계산된 값을 찾고 합계 표현의 가능한 모든 조합을 인쇄합니다.

이 솔루션은 약간 복잡하고 시간 복잡도는 다음과 같습니다.
O( (a*b) 4 ).

우리 솔루션의 작동을 설명하는 프로그램,

예시

#include <bits/stdc++.h>
using namespace std;

void findEulerSquareNumberValue(int a, int b) {

   int prod = a * b;
   int sumSquare = 0;
   for (int x = 0; x <= sqrt(prod); x++) {
      for (int y = x; y <= sqrt(prod); y++) {
         for (int z = y; z <= sqrt(prod); z++) {
            for (int k = z; k <= sqrt(prod); k++) {
           
               sumSquare = (x*x) + (y*y) + (z*z) + (k*k);
               if (sumSquare == prod) {
                cout<<"The product "<<a<<"*"<<b<<" = "<<prod<<" represented as ";
                cout<<x<<"*"<<x<<" + ";
                cout<<y<<"*"<<y<<" + ";
                cout<<z<<"*"<<z<<" + ";
                cout<<k<<"*"<<k<<endl;
                cout<<endl;
               }
            }
         }
      }
   }
}

int main() {

   int a = (2*2) + (3*3) + (4*4) + (5*5);
   int b = (1*1) + (2*2) + (1*1) + (2*2);
   cout<<"a = (2*2) + (3*3) + (4*4) + (5*5) = "<<a<<endl;
   cout<<"b = (1*1) + (2*2) + (1*1) + (2*2) = "<<b<<endl;
   findEulerSquareNumberValue(a, b);
   
   return 0;
}

출력 -

a = (2*2) + (3*3) + (4*4) + (5*5) = 54
b = (1*1) + (2*2) + (1*1) + (2*2) = 10
The product 54*10 = 540 represented as 1*1 + 1*1 + 3*3 + 23*23

The product 54*10 = 540 represented as 1*1 + 3*3 + 13*13 + 19*19

The product 54*10 = 540 represented as 1*1 + 5*5 + 15*15 + 17*17

The product 54*10 = 540 represented as 1*1 + 7*7 + 7*7 + 21*21

The product 54*10 = 540 represented as 1*1 + 9*9 + 13*13 + 17*17

The product 54*10 = 540 represented as 2*2 + 4*4 + 6*6 + 22*22

The product 54*10 = 540 represented as 2*2 + 4*4 + 14*14 + 18*18

The product 54*10 = 540 represented as 2*2 + 6*6 + 10*10 + 20*20

The product 54*10 = 540 represented as 2*2 + 12*12 + 14*14 + 14*14

The product 54*10 = 540 represented as 3*3 + 3*3 + 9*9 + 21*21

The product 54*10 = 540 represented as 3*3 + 7*7 + 11*11 + 19*19

The product 54*10 = 540 represented as 3*3 + 9*9 + 15*15 + 15*15

The product 54*10 = 540 represented as 3*3 + 11*11 + 11*11 + 17*17

The product 54*10 = 540 represented as 4*4 + 10*10 + 10*10 + 18*18

The product 54*10 = 540 represented as 5*5 + 5*5 + 7*7 + 21*21

The product 54*10 = 540 represented as 5*5 + 11*11 + 13*13 + 15*15

The product 54*10 = 540 represented as 6*6 + 6*6 + 12*12 + 18*18

The product 54*10 = 540 represented as 7*7 + 7*7 + 9*9 + 19*19

The product 54*10 = 540 represented as 7*7 + 9*9 + 11*11 + 17*17

The product 54*10 = 540 represented as 9*9 + 11*11 + 13*13 + 13*13

The product 54*10 = 540 represented as 10*10 + 10*10 + 12*12 + 14*14

다른 시간 복잡도가 적은 문제를 해결하는 방법은 세 개의 중첩 루프를 사용하고 네 번째 값을 확인하는 것입니다. 나머지 숫자가 완전제곱수이면 근값이 네 번째 숫자입니다. 그렇지 않으면 솔루션이 불가능합니다. 이 방법은 아마도 네 번째 루프를 제거하고 솔루션을 효과적으로 만들 것입니다.

우리 솔루션의 작동을 설명하는 프로그램,

예시

#include <bits/stdc++.h>
using namespace std;

void findEulerSquareNumberValue(int a, int b) {

   int prod = a * b;
   int sumSquare = 0;
   for (int x = 0; x <= sqrt(prod); x++) {
      for (int y = x; y <= sqrt(prod); y++) {
         for (int z = y; z <= sqrt(prod); z++) {
         
            sumSquare = (x*x) + (y*y) + (z*z);
            float k = sqrt(prod - sumSquare);
            if ( floor(k) == ceil(k)) {
             cout<<"The product "<<a<<"*"<<b<<" = "<<prod<<" represented as ";
             cout<<x<<"*"<<x<<" + ";
             cout<<y<<"*"<<y<<" + ";
             cout<<z<<"*"<<z<<" + ";
             cout<<k<<"*"<<k<<endl;
             cout<<endl;
            }
         }
      }
   }
}

int main() {

   int a = (2*2) + (3*3) + (4*4) + (5*5);
   int b = (1*1) + (2*2) + (1*1) + (2*2);
   cout<<"a = (2*2) + (3*3) + (4*4) + (5*5) = "<<a<<endl;
   cout<<"b = (1*1) + (2*2) + (1*1) + (2*2) = "<<b<<endl;
   findEulerSquareNumberValue(a, b);
   
   return 0;
}

출력 -

a = (2*2) + (3*3) + (4*4) + (5*5) = 54
b = (1*1) + (2*2) + (1*1) + (2*2) = 10
The product 54*10 = 540 represented as 1*1 + 1*1 + 3*3 + 23*23

The product 54*10 = 540 represented as 1*1 + 1*1 + 23*23 + 3*3

The product 54*10 = 540 represented as 1*1 + 3*3 + 13*13 + 19*19

The product 54*10 = 540 represented as 1*1 + 3*3 + 19*19 + 13*13

The product 54*10 = 540 represented as 1*1 + 3*3 + 23*23 + 1*1

The product 54*10 = 540 represented as 1*1 + 5*5 + 15*15 + 17*17

The product 54*10 = 540 represented as 1*1 + 5*5 + 17*17 + 15*15

The product 54*10 = 540 represented as 1*1 + 7*7 + 7*7 + 21*21

The product 54*10 = 540 represented as 1*1 + 7*7 + 21*21 + 7*7

The product 54*10 = 540 represented as 1*1 + 9*9 + 13*13 + 17*17

The product 54*10 = 540 represented as 1*1 + 9*9 + 17*17 + 13*13

The product 54*10 = 540 represented as 1*1 + 13*13 + 17*17 + 9*9

The product 54*10 = 540 represented as 1*1 + 13*13 + 19*19 + 3*3

The product 54*10 = 540 represented as 1*1 + 15*15 + 17*17 + 5*5

The product 54*10 = 540 represented as 2*2 + 4*4 + 6*6 + 22*22

The product 54*10 = 540 represented as 2*2 + 4*4 + 14*14 + 18*18

The product 54*10 = 540 represented as 2*2 + 4*4 + 18*18 + 14*14

The product 54*10 = 540 represented as 2*2 + 4*4 + 22*22 + 6*6

The product 54*10 = 540 represented as 2*2 + 6*6 + 10*10 + 20*20

The product 54*10 = 540 represented as 2*2 + 6*6 + 20*20 + 10*10

The product 54*10 = 540 represented as 2*2 + 6*6 + 22*22 + 4*4

The product 54*10 = 540 represented as 2*2 + 10*10 + 20*20 + 6*6

The product 54*10 = 540 represented as 2*2 + 12*12 + 14*14 + 14*14

The product 54*10 = 540 represented as 2*2 + 14*14 + 14*14 + 12*12

The product 54*10 = 540 represented as 2*2 + 14*14 + 18*18 + 4*4

The product 54*10 = 540 represented as 3*3 + 3*3 + 9*9 + 21*21

The product 54*10 = 540 represented as 3*3 + 3*3 + 21*21 + 9*9

The product 54*10 = 540 represented as 3*3 + 7*7 + 11*11 + 19*19

The product 54*10 = 540 represented as 3*3 + 7*7 + 19*19 + 11*11

The product 54*10 = 540 represented as 3*3 + 9*9 + 15*15 + 15*15

The product 54*10 = 540 represented as 3*3 + 9*9 + 21*21 + 3*3

The product 54*10 = 540 represented as 3*3 + 11*11 + 11*11 + 17*17

The product 54*10 = 540 represented as 3*3 + 11*11 + 17*17 + 11*11

The product 54*10 = 540 represented as 3*3 + 11*11 + 19*19 + 7*7

The product 54*10 = 540 represented as 3*3 + 13*13 + 19*19 + 1*1

The product 54*10 = 540 represented as 3*3 + 15*15 + 15*15 + 9*9

The product 54*10 = 540 represented as 4*4 + 6*6 + 22*22 + 2*2

The product 54*10 = 540 represented as 4*4 + 10*10 + 10*10 + 18*18

The product 54*10 = 540 represented as 4*4 + 10*10 + 18*18 + 10*10

The product 54*10 = 540 represented as 4*4 + 14*14 + 18*18 + 2*2

The product 54*10 = 540 represented as 5*5 + 5*5 + 7*7 + 21*21

The product 54*10 = 540 represented as 5*5 + 5*5 + 21*21 + 7*7

The product 54*10 = 540 represented as 5*5 + 7*7 + 21*21 + 5*5

The product 54*10 = 540 represented as 5*5 + 11*11 + 13*13 + 15*15

The product 54*10 = 540 represented as 5*5 + 11*11 + 15*15 + 13*13

The product 54*10 = 540 represented as 5*5 + 13*13 + 15*15 + 11*11

The product 54*10 = 540 represented as 5*5 + 15*15 + 17*17 + 1*1

The product 54*10 = 540 represented as 6*6 + 6*6 + 12*12 + 18*18

The product 54*10 = 540 represented as 6*6 + 6*6 + 18*18 + 12*12

The product 54*10 = 540 represented as 6*6 + 10*10 + 20*20 + 2*2

The product 54*10 = 540 represented as 6*6 + 12*12 + 18*18 + 6*6

The product 54*10 = 540 represented as 7*7 + 7*7 + 9*9 + 19*19

The product 54*10 = 540 represented as 7*7 + 7*7 + 19*19 + 9*9

The product 54*10 = 540 represented as 7*7 + 7*7 + 21*21 + 1*1

The product 54*10 = 540 represented as 7*7 + 9*9 + 11*11 + 17*17

The product 54*10 = 540 represented as 7*7 + 9*9 + 17*17 + 11*11

The product 54*10 = 540 represented as 7*7 + 9*9 + 19*19 + 7*7

The product 54*10 = 540 represented as 7*7 + 11*11 + 17*17 + 9*9

The product 54*10 = 540 represented as 7*7 + 11*11 + 19*19 + 3*3

The product 54*10 = 540 represented as 9*9 + 11*11 + 13*13 + 13*13

The product 54*10 = 540 represented as 9*9 + 11*11 + 17*17 + 7*7

The product 54*10 = 540 represented as 9*9 + 13*13 + 13*13 + 11*11

The product 54*10 = 540 represented as 9*9 + 13*13 + 17*17 + 1*1

The product 54*10 = 540 represented as 9*9 + 15*15 + 15*15 + 3*3

The product 54*10 = 540 represented as 10*10 + 10*10 + 12*12 + 14*14

The product 54*10 = 540 represented as 10*10 + 10*10 + 14*14 + 12*12

The product 54*10 = 540 represented as 10*10 + 10*10 + 18*18 + 4*4

The product 54*10 = 540 represented as 10*10 + 12*12 + 14*14 + 10*10

The product 54*10 = 540 represented as 11*11 + 11*11 + 17*17 + 3*3

The product 54*10 = 540 represented as 11*11 + 13*13 + 13*13 + 9*9

The product 54*10 = 540 represented as 11*11 + 13*13 + 15*15 + 5*5

The product 54*10 = 540 represented as 12*12 + 14*14 + 14*14 + 2*2