锐客网

  1. 首页 > it技术 > >

#|牛客编程巅峰赛S1第12场 王者C-椭圆曲线（快速乘的运用）

#快速乘牛客巅峰赛

题目链接：https://ac.nowcoder.com/acm/contest/6916/C
博客园食用链接：https://www.cnblogs.com/lonely-wind-/p/13512283.html
题目描述
椭圆曲线加密算法是在椭圆曲线有限域上进行加密的算法，一般的椭圆曲线为 E p ( a , b ) : y 2 = x 3 + a x + b E_{p}(a,b): y^2=x^3+ax+b Ep?(a,b):y2=x3+ax+b，其中p为质数。
椭圆曲线上的点的运算满足以下规则:
1.曲线上A、B不同两点相加，过A、B两点画一条直线，找到直线与椭圆曲线的交点，交点关于x轴对称位置的点，定义为A+B，即为加法。如下图所示：A + B = C
#|牛客编程巅峰赛S1第12场 王者C-椭圆曲线（快速乘的运用）
文章图片

2.相同点A与A相加，过A点做切线，与椭圆曲线的交点，交点关于x轴对称位置的点，定义为A + A，即2A，即为二倍运算。
#|牛客编程巅峰赛S1第12场 王者C-椭圆曲线（快速乘的运用）
文章图片

E p ( a , b ) : y 2 = x 3 + a x + b E_{p}(a,b): y^2=x^3+ax+b Ep?(a,b):y2=x3+ax+b， P ( x 1 , x 2 ) , Q ( x 2 , y 2 ) , R ( x 3 , y 3 ) P(x_1,x_2),Q(x_2,y_2),R(x_3,y_3) P(x1?,x2?),Q(x2?,y2?),R(x3?,y3?)，其中R=P+Q，有
x 3 ≡ k 2 ? x 1 ? x 2 ? ( m o d ? p ) x_3\equiv k^2-x_1-x_2\: (mod\: p) x3?≡k2?x1??x2?(modp)
y 3 ≡ k ( x 1 ? x 3 ) ? y 1 ? ( m o d ? p ) y_3\equiv k(x_1-x_3)-y_1\: (mod\: p) y3?≡k(x1??x3?)?y1?(modp)
若P=Q,则 k = 3 x 1 2 + a 2 y 1 ? ( m o d ? p ) k=\frac{3x_1^2+a}{2y_1}\: (mod\: p) k=2y1?3x12?+a?(modp)
若 P ≠ Q P\neq Q P?=Q,则 k = y 2 ? y 1 x 2 ? x 1 ? ( m o d ? p ) k=\frac{y_2-y_1}{x_2-x_1}\: (mod\: p) k=x2??x1?y2??y1??(modp)
现有 E p ( 1 , 1 ) E_p(1,1) Ep?(1,1),其中p=1000000007，牛牛得到了点 P ( x 1 , y 1 ) P(x_1,y_1) P(x1?,y1?)，你能告诉她n P \ nPnP是多少吗。
输入
(0,1),3
输出
(72,611)
备注:
0 ≤ x 1 , y 1 ≤ 1 0 9 0\leq x_1,y_1\leq 10^9 0≤x1?,y1?≤109， 1 ≤ n ≤ 1 0 9 1\leq n\leq 10^9 1≤n≤109
题目的意思是让你求 P + P + P + P + . . . + P P+P+P+P+...+P P+P+P+P+...+P的值，而这些运算可以通过上面的公式得到，只不过有点伤人的是，n的范围在 1 e 9 1e9 1e9，所以我们不能直接暴力地一个一个加，那么我们可以想到快速乘（实际上本质是个加法运算），这个东西就很方便了。。。只不过它满不满足快速乘就不太清楚了，只不过可以冲一波。然后就愉快地发现。。。A了。
【#|牛客编程巅峰赛S1第12场 王者C-椭圆曲线（快速乘的运用）】以下是AC代码：

/** * struct Point { * int x; * int y; * }; */ typedef long long ll; const int mod=1e9+7; class Solution { public: /** * * @param P Point类 * @param n int整型 * @return Point类 */ ll qpow(ll a,ll b){ ll ans=1; a%=mod; while (b){ if (b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; }ll pw(ll x) {return x*x%mod; }Point Plus(Point a,Point b) { ll x1=a.x,x2=b.x,y1=a.y,y2=b.y; if (x1==x2 && y1==y2){ ll k=(3LL*pw(x1)+1)%mod*qpow(2LL*y1,mod-2)%mod; int x3=(pw(k)-((x1+x2)%mod)+mod)%mod; int y3=(k*(x1-x3+mod)%mod-y1+mod)%mod; return Point{x3,y3}; } else { ll k=(y2-y1+mod)%mod*qpow((x2-x1+mod),mod-2)%mod; int x3=(pw(k)-((x1+x2)%mod)+mod)%mod; int y3=(k*(x1-x3+mod)%mod-y1+mod)%mod; return Point{x3,y3}; } }Point multi(Point a,int b) { Point ans=a; b--; while (b){ if (b&1) ans=Plus(ans,a); a=Plus(a,a); b>>=1; } return ans; }Point NTimesPoint(Point P, int n) { return multi(P,n); } };

    推荐阅读


    上一篇：WEB前端|用HTML5canvas绘制一个圆环形的进度表示

    下一篇：力扣 79.单词搜索+212.单词搜索II