結果

問題 No.344 ある無理数の累乗
ユーザー r_dream0r_dream0
提出日時 2017-02-22 21:55:05
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,037 bytes
コンパイル時間 707 ms
コンパイル使用メモリ 73,236 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-29 01:38:22
合計ジャッジ時間 2,212 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 1 ms
4,376 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 1 ms
4,380 KB
testcase_21 AC 1 ms
4,380 KB
testcase_22 AC 2 ms
4,380 KB
testcase_23 AC 1 ms
4,380 KB
testcase_24 AC 1 ms
4,380 KB
testcase_25 AC 2 ms
4,380 KB
testcase_26 AC 2 ms
4,380 KB
testcase_27 AC 2 ms
4,376 KB
testcase_28 AC 1 ms
4,376 KB
testcase_29 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;
// (1+sqrt(3)) ^ n + (1 - sqrt(3)) ^ nは次のような数列になる
// 2, 2, 8, 20, 56, 152, ... f(n+2)=2(f(n + 1) + f(n))
// -1 < (1 - sqrt(3)) ^ n < 1より上の数列の値-1か+0が求める整数
// 
const int64_t MOD = 1000;
void next(vector<long> &x, const vector<long> &first, long MOD) {
  long last = x.back();
  for(int i = x.size() - 2;  i >= 0 ; i--) x[i + 1] = x[i];
  x[0] = 0;
  for(int i = 0; i < x.size(); i++) x[i] = (MOD + x[i] - (long)last * first[i] % MOD) % MOD;
}

vector<long> next2N(const vector<long> &x, const vector<long> &first, long MOD) {
  vector<long> tmp(x);
  vector<long> result(x.size());
  for(int i = 0; i < x.size(); i++) {
    for(int j = 0; j < tmp.size(); j++) {
      result[j] = (result[j] + MOD - x[i] * tmp[j]) % MOD;
    }
    next(tmp, first, MOD);
  }
  return result;
}
long calc(const vector<long> &poly, const vector<long> &x, long MOD, int ofs = 0) {
  __int128_t ret = 0;
  for(int i = 0; i < poly.size(); i++) {
    ret += x[i + ofs] * poly[i] % MOD;
    ret %= MOD;
  }
  return (MOD - ret) % MOD;
}
long kitamasa(const vector<long> &poly, const vector<long> &x, int64_t N, long MOD) {
  if(N < poly.size()) return x[N];
  int t = poly.size(), l = 0;
  while(t > 0) t >>= 1, l++;
  for(int i = 0; i <= l; i++) {
    if(N >> (63 - __builtin_clzl(N) - l + i) & 1) {
      t |= 1LL << i;
    }
  }
  long cur = poly.size();
  vector<long> curPoly = poly;
  vector<long> poy2 = poly;
  while(cur < t) {
    if(cur == N) {
      return calc(curPoly, x, MOD);
    }
    next(curPoly, poly, MOD);
    cur++;
  }
  vector<long> ret(curPoly.size());
  cur = 0;
  for(int i = 63 - __builtin_clzl(N) - l - 1; i >= 0; i--) {
    curPoly = next2N(curPoly, poly, MOD);
    if(N >> i & 1) next(curPoly, poly, MOD);
  }
  return calc(curPoly, x, MOD);
}

int main() {
  int n;
  cin >> n;
  vector<int64_t> poly(2, -2);
  vector<int64_t> iv(2, 2);
  cout << (kitamasa(poly, iv, n, MOD) + (n % 2 == 0 ? MOD - 1 : 0)) % MOD<< endl;
}
0