#include <iostream>
#include <complex>
#include <cmath>
#include <vector>
using namespace std;
using Complex = complex<double>;  // 定义复数类型

// 生成n次单位根（k从0到n-1）
vector<Complex> generateUnitRoots(int n) {
    vector<Complex> roots(n);
    double angle = 2.0 * M_PI / n; // 每个相邻单位根之间的角度差
    for (int k = 0; k < n; ++k) {
        // 欧拉公式：e^(i*theta) = cos(theta) + i*sin(theta)
        roots[k] = Complex(cos(angle * k), sin(angle * k));
    }
    return roots;
}

int main() {
    int n = 8; // 测试8次单位根
    auto roots = generateUnitRoots(n);

    cout << n << "次单位根：" << endl;
    for (int k = 0; k < n; ++k) {
        // 输出实部+虚部，例如 (0.707107,0.707107)
        cout << "k=" << k << ": " << roots[k] << endl;
    }

    // 验证性质1：每个根的n次幂等于1（浮点误差下接近1+0i）
    cout << "\n验证 (omega^k)^8 = 1：" << endl;
    for (int k = 0; k < n; ++k) {
        Complex power = pow(roots[k], n); // 用pow函数
        cout << "k=" << k << ": " << power << endl;
    }

    // 验证性质2：折半定理 omega_{2n}^{2k} = omega_n^k
    int n2 = 2 * n;
    auto roots2n = generateUnitRoots(n2);
    cout << "\n验证折半定理：" << endl;
    for (int k = 0; k < n; ++k) {
        Complex left = roots2n[2 * k]; // omega_{2n}^{2k}
        Complex right = roots[k];      // omega_n^k
        // 计算两个复数的模差，应该接近0
        double diff = abs(left - right);
        cout << "k=" << k << ": omega_{2n}^{2k} = " << left
             << ", omega_n^k = " << right
             << ", 差=" << diff << endl;
    }

    // 额外验证：对称性 omega_n^{-k} = conj(omega_n^k)
    cout << "\n验证对称性 omega_n^{n-k} = conj(omega_n^k)：" << endl;
    for (int k = 1; k < n; ++k) {
        Complex w_k = roots[k];
        Complex w_n_minus_k = roots[n - k]; // omega_n^{n-k} 等价于 omega_n^{-k}
        Complex conj_w_k = conj(w_k);       // 共轭
        double diff = abs(w_n_minus_k - conj_w_k);
        cout << "k=" << k << ": diff=" << diff << endl;
    }

    return 0;
}

import cmath
import math

def generate_unit_roots(n):
    """生成n次单位根，返回复数列表"""
    roots = []
    angle = 2 * math.pi / n
    for k in range(n):
        # cmath.rect(r, phi) 将极坐标转为直角坐标
        root = cmath.rect(1, angle * k)  # 模长为1，幅角为 angle*k
        roots.append(root)
    return roots

def test_unit_roots():
    n = 8
    roots = generate_unit_roots(n)
    print(f"{n}次单位根：")
    for k, r in enumerate(roots):
        print(f"k={k}: {r:.4f}")  # 保留4位小数

    # 验证性质1：每个根的n次幂接近1
    print("\n验证 (omega^k)^8 = 1：")
    for k, r in enumerate(roots):
        power = r ** n
        print(f"k={k}: {power:.4f}")

    # 验证折半定理
    n2 = 2 * n
    roots2n = generate_unit_roots(n2)
    print("\n验证折半定理：")
    for k in range(n):
        left = roots2n[2 * k]
        right = roots[k]
        diff = abs(left - right)
        print(f"k={k}: left={left:.4f}, right={right:.4f}, diff={diff:.2e}")

    # 验证周期性 omega_n^{k+n} = omega_n^k
    print("\n验证周期性：")
    for k in range(1, n):
        w_k_plus_n = roots[(k + n) % n]  # 因为周期，取模
        diff = abs(roots[k] - w_k_plus_n)
        print(f"k={k}: diff={diff:.2e}")

if __name__ == "__main__":
    test_unit_roots()