QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#51608 | #4634. Factor | Hongzy | WA | 1134ms | 8996kb | C++ | 1.1kb | 2022-10-02 23:23:21 | 2022-10-02 23:23:23 |
Judging History
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'