洛谷的评测机有问题——P4213
  • 板块工单反馈版
  • 楼主cade
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/5/29 09:24
  • 上次更新2023/10/28 00:24:11
查看原帖
洛谷的评测机有问题——P4213
357360
cade楼主2022/5/29 09:24

最后一个test总是Runtime Error。floating point exception。经过测试,评测会出现x >= l > 0,但是x / l == 0这种情况

随便找了一份,代码如下:

#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define N 6000010
using namespace std;
template<typename T>inline void read(T& x)
{
  x = 0;
  static int p;p = 1;
  static char c;c = getchar();
  while (!isdigit(c)) { if (c == '-')p = -1;c = getchar(); }
  while (isdigit(c)) { x = (x << 1) + (x << 3) + (c - 48);c = getchar(); }
  x *= p;
}
bool vis[N];
int mu[N], sum1[N], phi[N];
long long sum2[N];
int cnt, prim[N];
tr1::unordered_map<long long, long long>w1;
tr1::unordered_map<int, int>w;
void get(int maxn)
{
  phi[1] = mu[1] = 1;
  for (int i = 2;i <= maxn;i++)
  {
    if (!vis[i])
    {
      prim[++cnt] = i;
      mu[i] = -1;phi[i] = i - 1;
    }
    for (int j = 1;j <= cnt && prim[j] * i <= maxn;j++)
    {
      vis[i * prim[j]] = 1;
      if (i % prim[j] == 0)
      {
        phi[i * prim[j]] = phi[i] * prim[j];
        break;
      }
      else mu[i * prim[j]] = -mu[i], phi[i * prim[j]] = phi[i] * (prim[j] - 1);
    }
  }
  for (int i = 1;i <= maxn;i++)sum1[i] = sum1[i - 1] + mu[i], sum2[i] = sum2[i - 1] + phi[i];
}
int djsmu(int x)
{
  if (x <= 6000000)return sum1[x];
  if (w[x])return w[x];
  int ans = 1;
  for (int l = 2, r;l >= 0 && l <= x;l = r + 1) {
    if (x <= 6000000) {
      exit(-4); //252
    }else if (l <= 0) {
      exit(-1); //255
    }
    else if (l > x) {
      exit(-2); //254
    }
    else if (x / l == 0) {
      exit(-3); //253
    }

    r = x / (x / l);
    ans -= (r - l + 1) * djsmu(x / l);
  }
  return w[x] = ans;
}
long long djsphi(long long x)
{
  if (x <= 6000000)return sum2[x];
  if (w1[x])return w1[x];
  long long ans = x * (x + 1) / 2;
  for (long long l = 2, r;l <= x;l = r + 1)
  {
    r = x / (x / l);
    ans -= (r - l + 1) * djsphi(x / l);
  }
  return w1[x] = ans;
}
int main()
{
  int t, n;
  read(t);
  get(6000000);
  while (t--)
  {
    read(n);
    printf("%lld %d\n", djsphi(n), djsmu(n));
  }
  return 0;
}

2022/5/29 09:24
加载中...