题目链接：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
文章图片
2.相同点A与A相加，过A点做切线，与椭圆曲线的交点，交点关于x轴对称位置的点，定义为A + A，即2A，即为二倍运算。
文章图片
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);
}
};
推荐阅读
- 数据结构和算法|LeetCode 的正确使用方式
- #|7.分布式事务管理
- #|算法设计与分析（Java实现）——贪心算法（集合覆盖案例）
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- #|阿尔法点亮LED灯(一）汇编语言
- #|Multimedia
- #|ARM裸机开发（汇编LED灯实验（I.MX6UL芯片））
- 基础课|使用深度优先搜索（DFS）、广度优先搜索（BFS）、A* 搜索算法求解 (n^2 -1) 数码难题，耗时与内存占用（时空复杂度）对比（附（(n^2 - 1) 数码问题控
- #|学习笔记 | Ch05 Pandas数据清洗 —— 缺失值、重复值、异常值
- win10|搏一搏 单车变摩托，是时候捣鼓一下家中的小米电视机啦。