QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#51607#4634. FactorHongzyTL 2207ms5144kbC++881b2022-10-02 23:14:372022-10-02 23:14:39

Judging History

This is the latest submission verdict.

  • [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:14:39]
  • Judged
  • Verdict: TL
  • Time: 2207ms
  • Memory: 5144kb
  • [2022-10-02 23:14:37]
  • Submitted

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;
    for(int j = 1; j <= pc && i * p[j] <= n; j ++) {
      tag[i * p[j]] = 1;
      if(i % p[j] == 0) break ;
    }
  }
}
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 ++) {
    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: 8ms
memory: 5024kb

input:

10

output:

5

result:

ok single line: '5'

Test #2:

score: 0
Accepted
time: 2ms
memory: 5096kb

input:

20

output:

9

result:

ok single line: '9'

Test #3:

score: 0
Accepted
time: 8ms
memory: 5020kb

input:

50

output:

17

result:

ok single line: '17'

Test #4:

score: 0
Accepted
time: 8ms
memory: 5144kb

input:

6

output:

4

result:

ok single line: '4'

Test #5:

score: 0
Accepted
time: 4ms
memory: 5052kb

input:

87

output:

26

result:

ok single line: '26'

Test #6:

score: 0
Accepted
time: 8ms
memory: 5092kb

input:

609

output:

130

result:

ok single line: '130'

Test #7:

score: 0
Accepted
time: 8ms
memory: 5116kb

input:

5126

output:

806

result:

ok single line: '806'

Test #8:

score: 0
Accepted
time: 8ms
memory: 4992kb

input:

92180

output:

10905

result:

ok single line: '10905'

Test #9:

score: 0
Accepted
time: 8ms
memory: 5024kb

input:

984096

output:

95960

result:

ok single line: '95960'

Test #10:

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

input:

5744387

output:

494209

result:

ok single line: '494209'

Test #11:

score: 0
Accepted
time: 22ms
memory: 5024kb

input:

51133311

output:

3851066

result:

ok single line: '3851066'

Test #12:

score: 0
Accepted
time: 201ms
memory: 5060kb

input:

607519174

output:

40319008

result:

ok single line: '40319008'

Test #13:

score: 0
Accepted
time: 2207ms
memory: 4988kb

input:

7739876803

output:

456270136

result:

ok single line: '456270136'

Test #14:

score: -100
Time Limit Exceeded

input:

80754680817

output:


result: