题解 | #椭圆曲线#

题意：

思路：这道题涉及乘法模逆元,。

将含有除法的模运算转化为乘法的模运算，设x是b的模逆元，则可化解为.。

根据费马小定理，

而

注意：这里数据类型要long long，否则会溢出。

思路：根据上面的椭圆曲线的加法公式，算出nP的值。

class Solution {
public:
    long long k;
    int MOD=1e9+7;
    Point NTimesPoint(Point P, int n) {
        Point res=P;//赋初值
        for(int i=1;i<n;i++){
            res=add(res,P);
        }
        return res;
    }
    
    Point add(Point p,Point q){
        if(p.x==q.x&&p.y==q.y){//P==Q
//             k=(3*(long long)p.x*p.x+1)/(2*p.y);
            k=(3*(long long)p.x%MOD*p.x%MOD+1)%MOD*quickPow(2*p.y%MOD, MOD-2)%MOD;
        }else{//P!=Q
//             k=(q.y-p.y)/(q.x-p.x);
            k=(f((long long)q.y,-p.y))*quickPow(f(q.x,-p.x),MOD-2)%MOD;
        }
        long long x=f(k*k,-p.x-q.x);
        long long y=f(k*f(p.x,-x),-p.y);
        return Point(x,y);
    }
    
    long long quickPow(long long a,long long p){//求a的模逆元用快速幂
        long long res=1;
        while(p){
            if(p&1)
                res=res%MOD*a%MOD;
            p>>=1;
            a=a%MOD*a%MOD;
        }
        return res;
    }
    
    long long f(long long x,long long y){//取模函数
        return (x+y+MOD)%MOD;//防止负数
    }
    
};

时间复杂度：

空间复杂度：

思路：计算nP，,如果循环n遍，会超时。

所以要用快速幂算法求解，将时间复杂度降为。

例：

class Solution {
public:
    long long k;
    int MOD=1e9+7;
    Point NTimesPoint(Point P, int n) {
        Point res=P;//赋初值
        n--;
        while(n){//将n快速幂->O（logn）
            if(n&1)//如果该二进制位是1,则加上
                res=add(res,P);
            P=add(P,P);//自加
            n>>=1;
        }
        return res;
    }
    
    Point add(Point p,Point q){
        if(p.x==q.x&&p.y==q.y){//P==Q
//             k=(3*(long long)p.x*p.x+1)/(2*p.y);
            k=(3*(long long)p.x%MOD*p.x%MOD+1)%MOD*quickPow(2*p.y%MOD, MOD-2)%MOD;
        }else{//P!=Q
//             k=(q.y-p.y)/(q.x-p.x);
            k=(f((long long)q.y,-p.y))*quickPow(f(q.x,-p.x),MOD-2)%MOD;
        }
        long long x=f(k*k,-p.x-q.x);
        long long y=f(k*f(p.x,-x),-p.y);
        return Point(x,y);
    }
    
    long long quickPow(long long a,long long p){//求a的模逆元用快速幂
        long long res=1;
        while(p){
            if(p&1)
                res=res%MOD*a%MOD;
            p>>=1;
            a=a%MOD*a%MOD;
        }
        return res;
    }
    
    long long f(long long x,long long y){//取模函数
        return (x+y+MOD)%MOD;//防止负数
    }
    
};

时间复杂度：

空间复杂度：