题解 | #椭圆曲线#

/**

• struct Point {
• int x;
• int y;
• };
• /

class Solution {
uint64_t Modp = 1000000007;
uint32_t Inv(uint64_t num)
{
uint32_t result = 1, Power = 1000000005;
while(Power > 0)
{
if(Power & 1)
result = result * num % Modp;
Power >>= 1;
num = num * num % Modp;
}
return result;
}
Point TwoTimesPoint(Point P)
{
Point R;
uint64_t k = (3 * (uint64_t)P.x * P.x + 1) % Modp * Inv(2 * P.y % Modp) % Modp;
R.x = (k * k + 2 * Modp - 2 * P.x) % Modp;
R.y = (k * (P.x + Modp - R.x) + Modp - P.y) % Modp;
return R;
}
Point TwoPointsAdd(Point P, Point Q)
{
Point R;
uint64_t k = (Q.y + Modp - P.y) * Inv((Q.x + Modp - P.x) % Modp) % Modp;
R.x = (k * k % Modp + 2 * Modp - P.x - Q.x) % Modp;
R.y = (k * (P.x + Modp - R.x) + Modp - P.y) % Modp;
return R;
}
public:
/**
*
* @param P Point类
* @param n int整型
* @return Point类
*/
Point NTimesPoint(Point P, int n) {
// write code here
Point PointTimes[30] = {P}, NP;
uint8_t NBin[30], Leath = 0, Flag = 0;
for( ; n > 0; Leath += 1)
{
NBin[Leath] = n & 1;
n >>= 1;
}
for(uint8_t i = 1; i < Leath; i += 1)
PointTimes[i] = TwoTimesPoint(PointTimes[i - 1]);
while(!NBin[Flag++]);
NP = PointTimes[Flag - 1];
for(uint8_t i = Flag; i < Leath; i++)
{
if(NBin[i])
NP = TwoPointsAdd(NP, PointTimes[i]);
}
return NP;
}
};