QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #48135 | #4634. Factor | DerekFeng | TL | 4331ms | 58048kb | C++ | 769b | 2022-09-11 19:46:16 | 2022-09-11 19:46:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7;
ll n,ans;bool f[N+4];
int tot,pri[N+4],num[N+4];
void init(){
for(int i=2;i<=N;i++){
if(!f[i])pri[++tot]=i;
for(int j=1;j<=tot&&pri[j]*i<=N;j++){
f[pri[j]*i]=1;
if(i%pri[j]==0)break;
}
}for(int i=2;i<=N;i++)num[i]=num[i-1]+(!f[i]);
}
void sol(int p,ll V,ll S){
if(pri[p]>S+1||V*pri[p]>n)return;
sol(p+1,V,S);
if(V*pri[p]*pri[p]<=n){
ll pw=pri[p],sum=pri[p]+1;V*=pri[p];
for(int tc=1;V<=n;tc++){
if(tc>1)ans++;
int pos=min(n/V,S*sum+1);
if(pos>pri[p])ans+=num[pos]-num[pri[p]];
sol(p+1,V,S*sum);
V*=pri[p],pw*=pri[p],sum+=pw;
}
}
}
int main(){
scanf("%lld",&n),init();
ans=n>1?2:1,sol(1,1,1),printf("%lld",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 53ms
memory: 56840kb
input:
10
output:
5
result:
ok single line: '5'
Test #2:
score: 0
Accepted
time: 46ms
memory: 56796kb
input:
20
output:
9
result:
ok single line: '9'
Test #3:
score: 0
Accepted
time: 54ms
memory: 56888kb
input:
50
output:
17
result:
ok single line: '17'
Test #4:
score: 0
Accepted
time: 49ms
memory: 56756kb
input:
6
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 59ms
memory: 56792kb
input:
87
output:
26
result:
ok single line: '26'
Test #6:
score: 0
Accepted
time: 67ms
memory: 56680kb
input:
609
output:
130
result:
ok single line: '130'
Test #7:
score: 0
Accepted
time: 56ms
memory: 56824kb
input:
5126
output:
806
result:
ok single line: '806'
Test #8:
score: 0
Accepted
time: 53ms
memory: 56892kb
input:
92180
output:
10905
result:
ok single line: '10905'
Test #9:
score: 0
Accepted
time: 56ms
memory: 56904kb
input:
984096
output:
95960
result:
ok single line: '95960'
Test #10:
score: 0
Accepted
time: 61ms
memory: 56840kb
input:
5744387
output:
494209
result:
ok single line: '494209'
Test #11:
score: 0
Accepted
time: 97ms
memory: 56924kb
input:
51133311
output:
3851066
result:
ok single line: '3851066'
Test #12:
score: 0
Accepted
time: 437ms
memory: 57124kb
input:
607519174
output:
40319008
result:
ok single line: '40319008'
Test #13:
score: 0
Accepted
time: 4331ms
memory: 58048kb
input:
7739876803
output:
456270136
result:
ok single line: '456270136'
Test #14:
score: -100
Time Limit Exceeded
input:
80754680817