QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #77687 | #5503. Euclidean Algorithm | chenshi# | TL | 1ms | 1764kb | C++ | 401b | 2023-02-15 12:57:42 | 2023-02-15 12:57:45 |
Judging History
answer
#include<cstdio>
using namespace std;
int z;long long n,ans;
inline long long sd(long long n){
long long res=0;
for(long long i=1,j;i<=n;i=j+1) j=n/(n/i),res+=n/i*(j-i+1ll);
return res;
}
int main(){
for(scanf("%d",&z);z--;printf("%lld\n",ans),ans=0){
scanf("%lld",&n);
ans=sd(n)-n;
for(long long i=2,j;i<=n;i=j+1) j=n/(n/i),ans+=n/i*(sd(j-1)-sd(i-2)-(j-i+1));
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 1764kb
input:
3 2 5 14
output:
1 9 62
result:
ok 3 lines
Test #2:
score: -100
Time Limit Exceeded
input:
3 29107867360 65171672278 41641960535