C ++中O（log n）中复数幂的程序

给定x + yi和整数n形式的复数；如果我们将复数乘以n，则任务是计算并打印复数的值。

什么是复数？

复数是可以以a + bi的形式写的数字，其中a和b是实数，而i是方程式的解，或者我们可以说一个虚数。因此，简单地说，我们可以说复数是实数和虚数的组合。

提高复数的幂

为了提高复数的幂，我们使用以下公式-

（a + bi）（c + di）=(ac-bd)+（ad + bc）i

就像我们有一个复数

2 + 3i并将其幂提高5，则我们将得到-

（2 + 3 i）⁵ =（2 + 3 i）（2 + 3i）（2 + 3 i）（2 + 3 i）（2 + 3i）

使用上面的公式，我们将得到答案-

示例

Input: x[0] = 10, x[1] = 11 /*Where x[0] is the first real number and 11 is the
second real number*/
n = 4
Output: -47959 + i(9240)
Input: x[0] = 2, x[1] =3
n = 5
Output: 122 + i(597)

我们用来解决上述问题的方法-

因此，可以使用迭代方法轻松解决问题，但是复杂度为O(n)，但是我们必须在O（log n）时间内解决问题。为此，我们可以-

首先以数组形式获取输入。
在功能上将x ^ n

检查n是否为1，然后返回x
递归调用幂传递x和n / 2，并将其结果存储在变量sq中。
检查n除以2是否剩下0；如果是这样，则返回从cmul(sq,sq)获得的结果
检查n除以2是否不剩下余数0；如果是这样，则返回从cmul（x，cmul(sq,sq)）获得的结果。

在功能上cmul()。

检查x1 = a + bi和x2 = x + di，然后x1 * x2 =（a * c–b * d）+（b * c + d * a）i。

返回并打印获得的结果。

算法

Start
Step 1-> declare function to calculate the product of two complex numbers
   long long* complex(long long* part1, long long* part2)
   Declare long long* ans = new long long[2]
   Set ans[0] = (part1[0] * part2[0]) - (part1[1] * part2[1])
   Se ans[1] = (part1[1] * part2[0]) + part1[0] * part2[1]
   return ans
Step 2-> declare将复数加到幂n的函数
   long long* power(long long* x, long long n)
   Declare long long* temp = new long long[2]
   IF n = 0
      Set temp[0] = 0
      Set temp[1] = 0
      return temp
   End
   IF n = 1
      return x
   End
   Declare long long* part = power(x, n / 2)
   IF n % 2 = 0
      return complex(part, part)
   End
   return complex(x, complex(part, part))
Step 3 -> In main()   Declare int n
   Declare and set long long* x = new long long[2]
   Set x[0] = 10
   Set x[1] = -11
   Set n = 4
   Call long long* a = power(x, n)
Stop

示例

#include <bits/stdc++.h>
using namespace std;
//计算两个复数的乘积
long long* complex(long long* part1, long long* part2) {
   long long* ans = new long long[2];
   ans[0] = (part1[0] * part2[0]) - (part1[1] * part2[1]);
   ans[1] = (part1[1] * part2[0]) + part1[0] * part2[1];
   return ans;
}
//将复数加到幂n的函数
long long* power(long long* x, long long n) {
   long long* temp = new long long[2];
   if (n == 0) {
      temp[0] = 0;
      temp[1] = 0;
      return temp;
   }
   if (n == 1)
      return x;
      long long* part = power(x, n / 2);
      if (n % 2 == 0)
         return complex(part, part);
         return complex(x, complex(part, part));
}
int main() {
   int n;
   long long* x = new long long[2];
   x[0] = 10;
   x[1] = -11;
   n = 4;
   long long* a = power(x, n);
   cout << a[0] << " + i ( " << a[1] << " )" << endl;
   return 0;
}

输出结果

power of complex number in O(Log n) : -47959 + i ( 9240 )

基础教程