QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#51608#4634. FactorHongzyWA 1134ms8996kbC++1.1kb2022-10-02 23:23:212022-10-02 23:23:23

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-02 23:23:23]
  • 评测
  • 测评结果:WA
  • 用时:1134ms
  • 内存:8996kb
  • [2022-10-02 23:23:21]
  • 提交

answer

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT);
#define rep(i, j, k) for(int i = j; i <= k; ++ i)
#define per(i, j, k) for(int i = j; i >= k; -- i)
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
bool tag[N];
int p[N], pc, s[N];
void sieve(int n) {
  rep(i, 2, n) {
    if(!tag[i]) p[++ pc] = i;
    s[i] = s[i-1] + (!tag[i]);
    for(int j = 1; j <= pc && i * p[j] <= n; j ++) {
      tag[i * p[j]] = 1;
      if(i % p[j] == 0) break ;
    }
  }
}
int range(int x, int y) {
  return x > y ? 0 : s[y] - s[x-1];
}
ll n, ans = 1;
void dfs(ll x, ll s, int id) {
  for(int i = id + 1; p[i] <= s+1 && x * p[i] <= n; i ++) {
    if(x * p[i] * p[i] > n) {
      ans += range(p[i], min(s+1, n / x));
      break;
    }
    ans++;
    ll z = 1, s0 = 1;
    rep(j, 1, 50) {
      z *= p[i], s0 += z;
      if(x * z > n) break;
      dfs(x * z, s * s0, i);
      if(j >= 2)
        ++ans;
    }
  }
}
int main() {
  sieve(1e6);
  scanf("%lld", &n);
  dfs(1, 1, 0);
  printf("%lld\n", ans);
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 8952kb

input:

10

output:

5

result:

ok single line: '5'

Test #2:

score: 0
Accepted
time: 10ms
memory: 8960kb

input:

20

output:

9

result:

ok single line: '9'

Test #3:

score: 0
Accepted
time: 6ms
memory: 8952kb

input:

50

output:

17

result:

ok single line: '17'

Test #4:

score: 0
Accepted
time: 5ms
memory: 8892kb

input:

6

output:

4

result:

ok single line: '4'

Test #5:

score: 0
Accepted
time: 5ms
memory: 8996kb

input:

87

output:

26

result:

ok single line: '26'

Test #6:

score: 0
Accepted
time: 11ms
memory: 8996kb

input:

609

output:

130

result:

ok single line: '130'

Test #7:

score: 0
Accepted
time: 10ms
memory: 8952kb

input:

5126

output:

806

result:

ok single line: '806'

Test #8:

score: 0
Accepted
time: 6ms
memory: 8992kb

input:

92180

output:

10905

result:

ok single line: '10905'

Test #9:

score: 0
Accepted
time: 10ms
memory: 8992kb

input:

984096

output:

95960

result:

ok single line: '95960'

Test #10:

score: 0
Accepted
time: 7ms
memory: 8964kb

input:

5744387

output:

494209

result:

ok single line: '494209'

Test #11:

score: 0
Accepted
time: 6ms
memory: 8996kb

input:

51133311

output:

3851066

result:

ok single line: '3851066'

Test #12:

score: 0
Accepted
time: 11ms
memory: 8896kb

input:

607519174

output:

40319008

result:

ok single line: '40319008'

Test #13:

score: 0
Accepted
time: 41ms
memory: 8956kb

input:

7739876803

output:

456270136

result:

ok single line: '456270136'

Test #14:

score: 0
Accepted
time: 185ms
memory: 8964kb

input:

80754680817

output:

4304423738

result:

ok single line: '4304423738'

Test #15:

score: -100
Wrong Answer
time: 1134ms
memory: 8940kb

input:

1000000000000

output:

47253446981

result:

wrong answer 1st lines differ - expected: '48366248808', found: '47253446981'