题解 | #椭圆曲线#

/**

• • 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;

  }
  };