QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#76869#5503. Euclidean AlgorithmTerryWangTL 1ms1568kbC111.0kb2023-02-12 14:23:012023-02-12 14:23:04

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-12 14:23:04]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:1568kb
  • [2023-02-12 14:23:01]
  • 提交

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';
	}
}

Details

Tip: Click on the bar to expand more detailed information

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

output:


result: