QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #31960 | #1175. Bags of Candies | Wu_Ren | TL | 17ms | 14732kb | C++14 | 888b | 2022-05-14 10:17:58 | 2022-05-14 10:17:58 |
Judging History
answer
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int m,K;
int pr[800010],p=0;
ll n,d[800010],f[800010];
int id[800010],id2[800010];
bool isnt[800010];
void init(int N){
for(int i=2;i<=N;i++){
if(!isnt[i]){
pr[++p]=i;
}
for(int j=1;j<=p&&pr[j]*i<=N;j++){
isnt[pr[j]*i]=1;
if(i%pr[j]==0) break;
}
}
}
int get(ll x){
return x<=m?id[x]:id2[n/x];
}
void work(ll n){
d[0]=0;
for(ll i=1,r;i<=n;i=r+1){
r=n/(n/i);
ll nw=n/i;
d[++d[0]]=nw,f[d[0]]=nw-1;
(nw<=m?id[nw]:id2[n/nw])=d[0];
}
for(int j=1;j<=p;j++){
ll ed=1ll*pr[j]*pr[j];
for(int i=1;d[i]>=ed;i++){
int t=get(d[i]/pr[j]);
f[i]=(f[i]-(f[t]-j+1));
}
}
}
void sol(){
scanf("%lld",&n),m=2*sqrtl(n);
work(n);
printf("%lld\n",n-(n-f[1]+f[get(n/2)]-1)/2);
}
int main(){
init(800005);
int T;
scanf("%d",&T);
while(T--) sol();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 9ms
memory: 14732kb
input:
2 4 9
output:
3 6
result:
ok 2 number(s): "3 6"
Test #2:
score: 0
Accepted
time: 9ms
memory: 12820kb
input:
5 2 3 4 5 6
output:
2 3 3 4 4
result:
ok 5 number(s): "2 3 3 4 4"
Test #3:
score: 0
Accepted
time: 5ms
memory: 14712kb
input:
5 1111 2018 3333 4006 5555
output:
599 1078 1772 2128 2942
result:
ok 5 number(s): "599 1078 1772 2128 2942"
Test #4:
score: 0
Accepted
time: 17ms
memory: 14420kb
input:
5 26666666 10000000 23456789 27777777 24444442
output:
13730373 5158034 12080298 14301448 12588059
result:
ok 5 number(s): "13730373 5158034 12080298 14301448 12588059"
Test #5:
score: -100
Time Limit Exceeded
input:
5 47890123456 12345678901 96666666669 85555555558 100000000000