QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #48027 | #4634. Factor | Pure_Furies | WA | 249ms | 56380kb | C++ | 686b | 2022-09-11 10:32:47 | 2022-09-11 10:32:50 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
long long n;
bool ispr[10000003];
int pr[1000003],m,ans;
int sum[10000003];
void solve(int i,long long nw,long long mul){
ans++;
for(int j=i+1;pr[j]-1<=mul&&nw*pr[j]<=n;j++){
if(nw*pr[j]*pr[j]>n){
ans+=sum[min(n/nw,mul+1)]-j+1;
break;
}
long long _nw=nw,pw=1,sum=1;
while(_nw*pr[j]<=n){
pw*=pr[j];
sum+=pw;
_nw*=pr[j];
solve(j,_nw,mul*sum);
}
}
}
int main(){
cin>>n;
memset(ispr,1,sizeof(ispr));
for(int i=2;i<=10000000;i++){
if(ispr[i]){
sum[i]=1;
pr[++m]=i;
for(int j=i;j<=10000000;j+=i)
ispr[j]=0;
}
sum[i]+=sum[i-1];
}
solve(0,1,1);
cout<<ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 81ms
memory: 56376kb
input:
10
output:
5
result:
ok single line: '5'
Test #2:
score: 0
Accepted
time: 76ms
memory: 55128kb
input:
20
output:
9
result:
ok single line: '9'
Test #3:
score: 0
Accepted
time: 92ms
memory: 55300kb
input:
50
output:
17
result:
ok single line: '17'
Test #4:
score: 0
Accepted
time: 77ms
memory: 56368kb
input:
6
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 84ms
memory: 56376kb
input:
87
output:
26
result:
ok single line: '26'
Test #6:
score: 0
Accepted
time: 75ms
memory: 54984kb
input:
609
output:
130
result:
ok single line: '130'
Test #7:
score: 0
Accepted
time: 66ms
memory: 55160kb
input:
5126
output:
806
result:
ok single line: '806'
Test #8:
score: 0
Accepted
time: 77ms
memory: 56276kb
input:
92180
output:
10905
result:
ok single line: '10905'
Test #9:
score: 0
Accepted
time: 77ms
memory: 55360kb
input:
984096
output:
95960
result:
ok single line: '95960'
Test #10:
score: 0
Accepted
time: 78ms
memory: 56368kb
input:
5744387
output:
494209
result:
ok single line: '494209'
Test #11:
score: 0
Accepted
time: 83ms
memory: 56096kb
input:
51133311
output:
3851066
result:
ok single line: '3851066'
Test #12:
score: 0
Accepted
time: 99ms
memory: 56252kb
input:
607519174
output:
40319008
result:
ok single line: '40319008'
Test #13:
score: 0
Accepted
time: 119ms
memory: 56380kb
input:
7739876803
output:
456270136
result:
ok single line: '456270136'
Test #14:
score: -100
Wrong Answer
time: 249ms
memory: 56252kb
input:
80754680817
output:
9456442
result:
wrong answer 1st lines differ - expected: '4304423738', found: '9456442'