NOIP 2005 普及组算法题解

const int n = 10;
const int ext = 30;
int ans = 0;
for (int i = 0; i < n; i++) {
  int v;
  scanf("%d", &v);
  if (v <= h + ext) {
    ans++;
  }
}
printf("%d\n", ans);

vector<int> nums(l + 1, 1);
while (m--) {
  int u, v;
  scanf("%d%d", &u, &v);
  for (int i = u; i <= v; i++) {
    nums[i] = 0;
  }
}
int ans = 0;
for (int i = 0; i <= l; i++) {
  ans += nums[i];
}
printf("%d\n", ans);

sort(intervals.begin(), intervals.end());
vector<pair<int, int>> merged;
for (auto [u, v] : intervals) {
  if (merged.empty() || merged.back().second < u) {
    merged.push_back({u, v});
  } else {
    merged.back().second = max(merged.back().second, v);
  }
}
int ans = l + 1;
for (auto [u, v] : merged) {
  ans -= (v - u + 1);
}
printf("%d\n", ans);

sort(intervals.begin(), intervals.end());
int ans = 0;
int pre = 0;  // [0, pre) 已被覆盖
for (auto [u, v] : intervals) {
  if (pre < u) {
    ans += u - pre;
  }
  pre = max(pre, v + 1);
}
if (pre <= l) {
  ans += l - pre + 1;
}
printf("%d\n", ans);

vector<int> dp(T + 1, 0);
while (M--) {
  int t, v;
  scanf("%d%d", &t, &v);
  for (int i = T; i >= t; i--) {
    dp[i] = max(dp[i], dp[i - t] + v);
  }
}
printf("%d\n", dp[T]);

ll K = 1;
for (int i = 0; i < k; i++) K *= 10;
unordered_map<ll, int> mp;
ll val = n % K;
mp[val] = 1;
int times = 1;
while (1) {
  val = val * n % K;
  times++;
  if (mp.count(val)) {
    printf("%d\n", times - mp[val]);
    break;
  }
  mp[val] = times;
}

BigNum n(s);
n.Smp(k);
BigNum val = n;
unordered_map<string, int> mp;
mp[val.ToString()] = 1;
int times = 1;
while (1) {
  val = val * n;
  val.Smp(k);
  times++;
  string s = val.ToString();
  if (mp.count(s)) {
    if (mp[s] == 1) {
      printf("%d\n", times - 1);
    } else {
      printf("-1\n");
    }
    break;
  }
  mp[s] = times;
}

ll TrySolver(const BigNum& nk, const int k, const ll preLoop) {
  unordered_map<string, int> mp;
  mp["1"] = 0;
  const BigNum loopVal = Pow(nk, preLoop, k);
  BigNum val(1);
  for (ll times = 1;; times++) {
    BigNum nextVal = val * loopVal;
    nextVal.Smp(k);
    const string s = nextVal.ToString();
    if (mp.count(s)) {
      if (mp[s] == 1) {
        // 重复第一个值，循环长度为 (times-1) * preLoop
        return (times - 1) * preLoop;
      } else if (mp[s] == 0) {
        // 变成了 1，循环长度为 times * preLoop
        return times * preLoop;
      }
      return -1;
    }
    val = nextVal;
    mp[s] = times;
  }
}

struct BigNum {
  vector<ll> data;  // 逆序存储
  BigNum(ll x = 0) {
    while (x) { data.push_back(x % 10); x /= 10; }
    if (data.empty()) data.push_back(0);
  }
  BigNum(const string& s) {
    for (int i = s.size() - 1; i >= 0; i--) data.push_back(s[i] - '0');
  }
  BigNum& Smp(int minBit = 0) {
    while (minBit > 0 && data.size() > minBit) data.pop_back();
    while (data.size() > 1 && data.back() == 0) data.pop_back();
    return *this;
  }
  BigNum operator*(const BigNum& other) const {
    BigNum res;
    res.data.resize(data.size() + other.data.size() + 1, 0);
    for (int i = 0; i < data.size(); i++) {
      int carry = 0, pos = i;
      for (int j = 0; j < other.data.size(); j++) {
        res.data[pos] += data[i] * other.data[j] + carry;
        carry = res.data[pos] / 10;
        res.data[pos] %= 10;
        pos++;
      }
      while (carry) {
        res.data[pos] += carry;
        carry = res.data[pos] / 10;
        res.data[pos] %= 10;
        pos++;
      }
    }
    return res.Smp();
  }
  string ToString() const {
    string res;
    for (int i = data.size() - 1; i >= 0; i--) res.push_back(data[i] + '0');
    return res;
  }
};

string ToString(BigNum n, int k) { n.Smp(k); return n.ToString(); }

BigNum preLoopNum;  // 当前循环长度（大整数）
BigNum preLoopVal;  // n^preLoopNum 的后 K 位
int K;

ll TrySolver(const BigNum& nk, const int k) {
  unordered_map<string, int> mp;
  const string oneString = ToString(nk, k);
  BigNum val(1);
  for (ll times = 1; times <= 11; times++) {  // 最多尝试 10 次
    BigNum nextVal = val * preLoopVal;
    nextVal.Smp(K);
    const string s = ToString(nextVal, k);
    if (mp.count(s)) {
      if (mp[s] == 1) {  // 重复的是第一个值
        if (ToString(val * nk, k) == oneString) {
          preLoopVal = val;
          preLoopNum = preLoopNum * BigNum(times - 1);
          return 0;
        }
        return -1;
      }
      return -1;  // 循环不包含起点
    }
    val = nextVal;
    mp[s] = times;
  }
  return -1;
}

void Solver() {
  char buf[222];
  scanf("%s%d", buf, &K);
  BigNum n(string(buf));
  n.Smp(K);
  preLoopNum = BigNum(1);
  preLoopVal = n;
  for (int k = 1; k <= K; k++) {
    if (TrySolver(n, k) == -1) {
      printf("-1\n");
      return;
    }
  }
  printf("%s\n", preLoopNum.ToString().c_str());
}