题意整理：

题目给出一个椭圆曲线 $E_p(1,1):y^2=x^3+x+1E\_p(1,1):y^2=x^3+x+1$Ep​(1,1):y2=x3+x+1,其中$p=1000000007p=1000000007$p=1000000007,以及一个点$P(x,y)P(x,y)$P(x,y)，求解$nPnP$nP的值。 椭圆曲线上的加法公式题目已经给出，既： 需要注意的是，其中出现了模p的除法，既模逆元，这部分模数相关的知识此处不做详细介绍，只给出一个求模的方法。 利用拓展欧几里得算法和费马小定理，可以得出对除法求模的递归方法， 当p是素数时，记$Inv\left(n\right)Inv(n)$Inv(n)为n对p的除法求模结果，有

$Inv\left(n\right)=(p-p/n)\ast Inv\left(p\%n\right)Inv(n)\; =\; (p\; -\; p\; /\; n)\; *\; In***)\; \%\; p$Inv(n)=(p−p/n)∗Inv(p%n),而递归终条件为 $Inv\left(1\right)=1Inv(1)=1$Inv(1)=1 知道这部分知识后，就可以对本题进行求解了。

方法一：暴力累加(超时)

核心思想：

题目已经给出了椭圆曲线上的加法公式，而椭圆曲线的加法满足结合律，所以$nPnP$nP实际上就是n个P结点相加即可

核心代码：

class Solution {
public:
    long long mod = 1000000007;
    int Inv(long long n) {
        //除法求模算法
        if(n == 1) return 1;
        return (mod - mod / n) * Inv(mod % n) % mod;
    }
    
    Point AddPoint(Point P, Point Q) {
        //两点相加算法
        uint64_t k;
        if(P.x == Q.x && P.y == Q.y) {
            //此时为2P
            k = (3 * (long long)P.x * P.x + 1) % mod * Inv(2 * P.y % mod) % mod;
        } else {
            k = (Q.y - P.y + mod) * Inv((Q.x - P.x + mod) % mod) % mod;
        }
        long long x = (k * k + 2 * mod - P.x - Q.x) % mod;
        long long y = (k * (P.x + mod - x) + mod - P.y) % mod;
        return Point((int)x, (int)y);
    }

    Point NTimesPoint(Point P, int n) {
        Point ans = P;
        for(int i = 1; i < n; ++i) {
            ans = AddPoint(ans, P);
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：$O\left(nlogn\right)O(nlogn)$O(nlogn)。既对n个P进行累加的开销,每次对$Inv\left(n\right)Inv(n)$Inv(n)的计算开销为$O\left(logn\right)O(logn)$O(logn),进行$n-1n-1$n−1次

空间复杂度：$O\left(logn\right)O(logn)$O(logn),主要是计算$Inv\left(n\right)Inv(n)$Inv(n)时的栈开销的上限，其他部分的开销均为常数个变量

方法二：

核心思想：

方法一时间复杂度很高，因为只是一直累加，且满足结合律，实际上对于大数的加法都有通用的方法，既快速幂。

核心代码：

class Solution {
public:
    long long mod = 1000000007;
    int Inv(long long n) {
        //除法求模算法
        if(n == 1) return 1;
        return (mod - mod / n) * Inv(mod % n) % mod;
    }
    
    Point AddPoint(Point P, Point Q) {
        //两点相加算法
        uint64_t k;
        if(P.x == Q.x && P.y == Q.y) {
            //此时为2P
            k = (3 * (long long)P.x * P.x + 1) % mod * Inv(2 * P.y % mod) % mod;
        } else {
            k = (Q.y - P.y + mod) * Inv((Q.x - P.x + mod) % mod) % mod;
        }
        long long x = (k * k + 2 * mod - P.x - Q.x) % mod;
        long long y = (k * (P.x + mod - x) + mod - P.y) % mod;
        return Point((int)x, (int)y);
    }

    Point NTimesPoint(Point P, int n) {
        Point ans;
        bool flag = true;
        while(n > 0) {
            //快速幂
            if(n % 2 == 1) {
                //第一次赋值时令ans=P,因为此处不能让ans=(0,0),椭圆曲线加法不存在零元
                ans = flag ? P : AddPoint(ans, P);
                flag = false;
            }
            n /= 2;
            P = AddPoint(P, P);
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：$O\left(\right(logn{)}^2)O((logn)^2)$O((logn)2)，n每次迭代都减小一半，故迭代次数为$O\left(logn\right)O(logn)$O(logn)，每次对$Inv\left(n\right)Inv(n)$Inv(n)的计算开销为$O\left(logn\right)O(logn)$O(logn)，总开销为$O\left(\right(logn{)}^2)O((logn)^2)$O((logn)2)

空间复杂度：$O\left(logn\right)O(logn)$O(logn),主要是计算$Inv\left(n\right)Inv(n)$Inv(n)时的栈开销的上限，其他部分的开销均为常数个变量