#61522 (C++11) No.308 素数は通れません

提出ソース

結果

問題	No.308 素数は通れません
ユーザー	moti
提出日時	2015-12-01 00:52:33
言語	C++11 (gcc 11.4.0)
結果	WA
実行時間	-
コード長	5,430 bytes
コンパイル時間	1,446 ms
コンパイル使用メモリ	109,592 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-09-14 05:36:29
合計ジャッジ時間	3,788 ms
ジャッジサーバーID （参考情報）	judge6 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	WA	-
testcase_45	WA	-
testcase_46	WA	-
testcase_47	WA	-
testcase_48	WA	-
testcase_49	WA	-
testcase_50	WA	-
testcase_51	WA	-
testcase_52	WA	-
testcase_53	WA	-
testcase_54	WA	-
testcase_55	WA	-
testcase_56	WA	-
testcase_57	WA	-
testcase_58	WA	-
testcase_59	WA	-
testcase_60	WA	-
testcase_61	WA	-
testcase_62	WA	-
testcase_63	WA	-
testcase_64	WA	-
testcase_65	WA	-
testcase_66	WA	-
testcase_67	WA	-
testcase_68	WA	-
testcase_69	WA	-
testcase_70	WA	-
testcase_71	WA	-
testcase_72	WA	-
testcase_73	WA	-
testcase_74	WA	-
testcase_75	WA	-
testcase_76	WA	-
testcase_77	WA	-
testcase_78	WA	-
testcase_79	WA	-
testcase_80	WA	-
testcase_81	WA	-
testcase_82	WA	-
testcase_83	WA	-
testcase_84	WA	-
testcase_85	WA	-
testcase_86	WA	-
testcase_87	WA	-
testcase_88	WA	-
testcase_89	WA	-
testcase_90	WA	-
testcase_91	WA	-
testcase_92	WA	-
testcase_93	WA	-
testcase_94	WA	-
testcase_95	WA	-
testcase_96	WA	-
testcase_97	WA	-
testcase_98	WA	-
testcase_99	WA	-
testcase_100	WA	-
testcase_101	WA	-
testcase_102	WA	-
testcase_103	WA	-
testcase_104	WA	-
testcase_105	WA	-
testcase_106	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>
#include <functional>
#include <numeric>
#include <bitset>

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define minimize(a, x) a = std::min(a, x)
#define maximize(a, x) a = std::max(a, x)

typedef long long ll;
int const inf = 1<<29;

typedef long long Int;
const Int B = 10000;      // base (power of 10)
const int BW = 4;         // log B
const int MAXDIGIT = 100; // it can represent 4*MAXDIGIT digits (in base 10)
struct BigNum {
  Int digit[MAXDIGIT];
  int size;
  BigNum(int size = 1, Int a = 0) : size(size) {
    memset(digit, 0, sizeof(digit));
    digit[0] = a;
  }
};
const BigNum ZERO(1, 0), ONE(1, 1);

// Comparators
bool operator<(BigNum x, BigNum y) {
  if (x.size != y.size) return x.size < y.size;
  for (int i = x.size-1; i >= 0; --i)
    if (x.digit[i] != y.digit[i]) return x.digit[i] < y.digit[i];
  return false;
}
bool operator >(BigNum x, BigNum y) { return y < x; }
bool operator<=(BigNum x, BigNum y) { return !(y < x); }
bool operator>=(BigNum x, BigNum y) { return !(x < y); }
bool operator!=(BigNum x, BigNum y) { return x < y || y < x; }
bool operator==(BigNum x, BigNum y) { return !(x < y) && !(y < x); }

// Utilities
BigNum normal(BigNum x) {
  Int c = 0;
  for (int i = 0; i < x.size; ++i) {
    while (x.digit[i] < 0)
      x.digit[i+1] -= 1, x.digit[i] += B;
    Int a = x.digit[i] + c;
    x.digit[i] = a % B;
    c          = a / B;
  }
  for (; c > 0; c /= B) x.digit[x.size++] = c % B;
  while (x.size > 1 && x.digit[x.size-1] == 0) --x.size;
  return x;
}
BigNum convert(Int a) {
  return normal(BigNum(1, a));
}
BigNum convert(const string &s) {
  BigNum x;
  int i = s.size() % BW;
  if (i > 0) i -= BW;
  for (; i < (int)s.size(); i += BW) {
    Int a = 0;
    for (int j = 0; j < BW; ++j)
      a = 10 * a + (i + j >= 0 ? s[i+j] - '0' : 0);
    x.digit[x.size++] = a;
  }
  reverse(x.digit, x.digit+x.size);
  return normal(x);
}
// Input/Output
ostream &operator<<(ostream &os, BigNum x) {
  os << x.digit[x.size-1];
  for (int i = x.size-2; i >= 0; --i)
    os << setw(BW) << setfill('0') << x.digit[i];
  return os;
}
istream &operator>>(istream &is, BigNum &x) {
  string s; is >> s;
  x = convert(s);
  return is;
}

// Basic Operations 
BigNum operator+(BigNum x, BigNum y) {
  if (x.size < y.size) x.size = y.size;
  for (int i = 0; i < y.size; ++i)
    x.digit[i] += y.digit[i];
  return normal(x);
}
BigNum operator-(BigNum x, BigNum y) {
  assert(x >= y);
  for (int i = 0; i < y.size; ++i)
    x.digit[i] -= y.digit[i];
  return normal(x);
}
BigNum operator*(BigNum x, BigNum y) {
  BigNum z(x.size + y.size);
  for (int i = 0; i < x.size; ++i)
    for (int j = 0; j < y.size; ++j)
      z.digit[i+j] += x.digit[i] * y.digit[j];
  return normal(z);
}
BigNum operator*(BigNum x, Int a) {
  for (int i = 0; i < x.size; ++i)
    x.digit[i] *= a;
  return normal(x);
}
pair<BigNum, Int> divmod(BigNum x, Int a) {
  Int c = 0, t;
  for (int i = x.size-1; i >= 0; --i) {
    t          = B * c + x.digit[i];
    x.digit[i] = t / a;
    c          = t % a;
  }
  return pair<BigNum, Int>(normal(x), c);
}
BigNum operator/(BigNum x, Int a) {
  return divmod(x, a).first;
}
Int operator%(BigNum x, Int a) {
  return divmod(x, a).second;
}
pair<BigNum, BigNum> divmod(BigNum x, BigNum y) {
  if (x.size < y.size) return pair<BigNum, BigNum>(ZERO, x);
  int F = B / (y.digit[y.size-1] + 1); // multiplying good-factor
  x = x * F; y = y * F;
  BigNum z(x.size - y.size + 1);
  for (int k = z.size-1, i = x.size-1; k >= 0; --k, --i) {
    z.digit[k]  = (i+1 < x.size ? x.digit[i+1] : 0) * B + x.digit[i];
    z.digit[k] /= y.digit[y.size-1];
    BigNum t(k + y.size);
    for (int m = 0; m < y.size; ++m)
      t.digit[k+m] = z.digit[k] * y.digit[m];
    t = normal(t);
    while (x < t) {
      z.digit[k] -= 1;
      for (int m = 0; m < y.size; ++m)
        t.digit[k+m] -= y.digit[m];
      t = normal(t);
    }
    x = x - t;
  }
  return pair<BigNum, BigNum>(normal(z), x / F);
}
BigNum operator/(BigNum x, BigNum y) {
  return divmod(x, y).first;
}
BigNum operator%(BigNum x, BigNum y) {
  return divmod(x, y).second;
}

// Advanced Operations
BigNum shift(BigNum x, int k) {
  if (x.size == 1 && x.digit[0] == 0) return x;
  x.size += k;
  for (int i = x.size - 1; i >= k; --i) x.digit[i] = x.digit[i-k];
  for (int i = k-1; i >= 0; --i) x.digit[i] = 0;
  return x;
}
BigNum sqrt(BigNum x) { // verified UVA 10023
  const BigNum _20 = convert(2*B);
  BigNum odd = ZERO;
  BigNum rem(2,0);
  BigNum ans = ZERO;
  for (int i = 2*((x.size-1)/2); i >= 0; i -= 2) {
    int group = (i+1 < x.size ? x.digit[i+1] : 0) * B + x.digit[i];
    odd =  _20 * ans + ONE;
    rem = shift(rem, 2) + convert(group);
    int count = 0;
    while (rem >= odd) {
      count = count + 1;
      rem = rem - odd;
      odd.digit[0] += 2;
      odd = normal(odd);
    }
    ans = shift(ans,1) + convert(count);
  }
  return ans;
}

int main() {

  BigNum N; cin >> N;

  cout << sqrt(N) << endl;

  return 0;
}

yukicoder

結果

テストケース

ソースコード