QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#222719#5503. Euclidean Algorithmucup-team859#AC ✓6908ms5904kbC++233.6kb2023-10-21 18:05:002023-10-21 18:05:01

Judging History

你现在查看的是最新测评结果

  • [2023-10-21 18:05:01]
  • 评测
  • 测评结果:AC
  • 用时:6908ms
  • 内存:5904kb
  • [2023-10-21 18:05:00]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;

#define int long long
using ll = long long;
using ull = unsigned long long;

string to_string(const string &s) {
  return '"' + s + '"';
}

string to_string(bool b) {
  return b ? "true" : "false";
}

template <typename A, typename B>
string to_string(const pair<A, B> &p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename T>
string to_string(const T &v) {
  string s = "{";
  bool first = true;
  for (const auto &it : v) {
    if (!first)
      s += ", ";
    else
      first = false;
    s += to_string(it);
  }
  return s += "}";
}

void debug_out() {
  cerr << endl;
}

template <typename T, typename... Args>
void debug_out(const T &first, const Args&... rest) {
  cerr << to_string(first) << " ";
  debug_out(rest...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

auto startTime = high_resolution_clock::now();
int get_time() {
  auto stopTime = chrono::high_resolution_clock::now();
  auto duration = duration_cast<milliseconds>(stopTime - startTime);
  return duration.count(); // in ms
}

int generate(int x, int y) {
  int gc = __gcd(x, y);

  map<int, int> f;
  f[x] = f[y] = 1;
  vector<int> v;
  v.push_back(x);
  v.push_back(y);

  int steps = 100, last = 100;
  int lim = 10 * max(x, y);
  while (last > 0) {
    --last;
    int x = v[rng() % v.size()]; 
    int y = v[rng() % v.size()]; 
    if (x == y)
      continue;

    if (2LL * x - y <= lim && 2LL * x - y >= gc && !f.count(2LL * x - y)) {
      v.push_back(2LL * x - y);
      last = 100;
      f[2LL * x - y] = 1;
    }

    swap(x, y);
    if (2LL * x - y <= lim && 2LL * x - y >= gc && !f.count(2LL * x - y)) {
      v.push_back(2LL * x - y);
      last = 100;
      f[2LL * x - y] = 1;
    }

    if (f.count(gc))
      return 1;

  }

  return f.count(gc) > 0;
}

int nrdiv(int x) {
  int nr = 0;
  for (int i = 1; i <= x; ++i) {
    if (x % i == 0)
      ++nr;
  }

  return nr;
}

const int sz = 316250;
vector <int> maxPrim;
void computeCiur() {
    maxPrim.resize(sz + 1);
    for (int i = 1; i <= sz; ++i)
      maxPrim[i] = 0;
    for (int i = 2; i <= sz; i++) {
        if (maxPrim[i] != 0) {
            continue;
        }
        for (int j = i; j <= sz; j += i) {
            maxPrim[j] = i;
        }
    }
}

int nrdiv_optim(int n) {
    if (n == 0)
      return 0;
    int frecv = 0, currPrim = -1, ans = 1;
    while (n != 1) {
        if (maxPrim[n] != currPrim) {
            ans *= (frecv + 1);
            frecv = 0;
        }
        currPrim = maxPrim[n];
        frecv++;
        n /= maxPrim[n];
    }
    ans *= (frecv + 1);
    return ans;
}

ll get_div_interval(int n) {
  int r = sqrt(n); 
  ll sum = 0;
  int last = n;
  for (int j = 1; j <= r; ++j) {
    int r = n / j;
    int l = n / (j + 1) + 1;

    last = l;

//    cout << n << " " << l << " " << r << " " << j << endl;
    sum += 1LL * j * (r - l + 1);

  }

  for (int j = 1; j < last; ++j)
    sum += n / j;

  return sum;
}

void solve() {
  ll n;
  cin >> n;

  ll sum = 0;
  int r = sqrt(n);
  for (int i = 1; i <= r; ++i) {
    sum += get_div_interval(n / i - 1);
  }

  for (int i = 1; i <= r; ++i) {
    sum += nrdiv_optim(i - 1) * (n / i - r);
  }
  
  cout << sum << endl;
}

int32_t main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  computeCiur();
  int t = 1;
  cin >> t;
  while (t--)
    solve();

  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 5736kb

input:

3
2
5
14

output:

1
9
62

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 3779ms
memory: 5648kb

input:

3
29107867360
65171672278
41641960535

output:

8921593237533
21300450379732
13136180138425

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 6728ms
memory: 5720kb

input:

3
90076809172
100000000000
99913139559

output:

30192292781431
33790187414013
33758574429172

result:

ok 3 lines

Test #4:

score: 0
Accepted
time: 6908ms
memory: 5904kb

input:

3
99997992652
99832769119
99997176887

output:

33789456663124
33729325483151
33789159765448

result:

ok 3 lines

Test #5:

score: 0
Accepted
time: 1756ms
memory: 5760kb

input:

30
500000004
991026973
875910473
804967563
817240034
859023503
871905363
994897763
533952899
999999996
500000003
851714124
618161807
500000002
500000000
642565501
703104463
520948789
513785485
999999997
1000000000
579195816
999999998
965942980
870891922
571793533
723494232
999999999
590539561
500000...

output:

106931694901
226252654431
197658605222
180202748830
183212809398
193491469207
196669619643
227219558906
114922441260
228494567273
106931693908
191690034392
134938724588
106931693896
106931693226
140788123843
155385451308
111856217326
110170204124
228494567397
228494568703
125643111389
228494567464
2...

result:

ok 30 lines

Test #6:

score: 0
Accepted
time: 695ms
memory: 5676kb

input:

3000
684920
881740
317776
310160
23336
999832
819596
973868
166
449876
290325
912538
999939
282224
600310
448121
816943
972518
895590
612220
349205
52931
999880
267637
549817
513310
182
852220
314635
377356
96591
628319
999757
597508
896048
116
71393
735158
203
282
68
33305
762621
745035
922434
5853...

output:

67611341
90223986
28005207
27233331
1319648
104127915
83003612
101051578
2569
41769873
25235715
93827427
104140754
24424464
58142642
41582414
82697155
100892535
91843138
59465231
31217321
3478468
104133259
22974376
52576328
48594603
2923
86785163
27686009
34130245
7039269
61257408
104119319
57832117...

result:

ok 3000 lines