QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#76869 | #5503. Euclidean Algorithm | TerryWang | TL | 1ms | 1568kb | C11 | 1.0kb | 2023-02-12 14:23:01 | 2023-02-12 14:23:04 |
Judging History
answer
#include<stdio.h>
typedef long long ll;
signed main(){
int T=1;
scanf("%d",&T);
for(;T--;){
ll n;
scanf("%lld",&n);
// if(n>10'000'000'000)n=10'000'000'000;
// auto brute1=[&](){
// ll res=0;
// for(ll g=1;g<=n;++g){
// for(ll i=1;i*g<=n;++i){
// for(ll j=i+1;j*g<=n;++j){
// if(!((j-1)%i))++res;
// }
// }
// }
// // std::cerr<<res<<'\n';
// return res;
// };
// auto brute2=[&](){
// ll res=0;
// for(ll g=1;g<=n;++g){
// for(ll i=1;i*g<=n;++i){
// res+=((n/g)-1)/i;
// }
// }
// // std::cerr<<res<<'\n';
// return res;
// };
// assert(brute1()==brute2());
ll ans=0;
for(ll l=1,r;l<=n;l=r+1){
ll val=n/l;
r=n/val;
{
ll res=0;
for(ll l=1,r;l<=(val-1);l=r+1){
// ++time;
ll val2=(val-1)/l;
r=(val-1)/val2;
res+=val2*(r-l+1);
}
ans+=res*(r-l+1);
}
}
// assert(ans==brute2());
printf("%lld\n",ans);
// std::cerr<<time<<'\n';
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 1568kb
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