QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#76906#5503. Euclidean Algorithmhe_ren_shi_lypAC ✓8934ms5244kbC++14805b2023-02-12 16:39:252023-02-12 16:39:26

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 16:39:26]
  • 评测
  • 测评结果:AC
  • 用时:8934ms
  • 内存:5244kb
  • [2023-02-12 16:39:25]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int MX = 4e5;
int mem[MX];

ll calc(ll n)
{
	if(n < MX && mem[n] != -1) return mem[n];
	
	ll sq = sqrt(n) + 2;
	while(sq * sq > n) --sq;
	
	ll res = 0, l = sq, r;
	for(int i=sq; i>=1; --i)
	{
		r = n / i;
		res += r + i * (r - l);
		l = r;
	}
	
	if(n < MX) mem[n] = res;
	return res;
}

void solve(void)
{
	ll n;
	scanf("%lld",&n);
	
	ll res = 0;
	for(ll l=1,r; l<=n; l=r+1)
	{
		ll k = n/l; r = n/k;
		res += calc(k-1) * (r-l+1);
	}
	printf("%lld\n",res);
}

int main(void)
{
//	freopen("E.in","r",stdin);
//	printf("%lf\n",(sizeof(mem)) / 1024.0 / 1024.0);
	
	memset(mem, -1, sizeof(mem));
	
	int T;
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 5244kb

input:

3
2
5
14

output:

1
9
62

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 4691ms
memory: 5100kb

input:

3
29107867360
65171672278
41641960535

output:

8921593237533
21300450379732
13136180138425

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 8904ms
memory: 5132kb

input:

3
90076809172
100000000000
99913139559

output:

30192292781431
33790187414013
33758574429172

result:

ok 3 lines

Test #4:

score: 0
Accepted
time: 8934ms
memory: 5088kb

input:

3
99997992652
99832769119
99997176887

output:

33789456663124
33729325483151
33789159765448

result:

ok 3 lines

Test #5:

score: 0
Accepted
time: 1071ms
memory: 5084kb

input:

30
500000004
991026973
875910473
804967563
817240034
859023503
871905363
994897763
533952899
999999996
500000003
851714124
618161807
500000002
500000000
642565501
703104463
520948789
513785485
999999997
1000000000
579195816
999999998
965942980
870891922
571793533
723494232
999999999
590539561
500000...

output:

106931694901
226252654431
197658605222
180202748830
183212809398
193491469207
196669619643
227219558906
114922441260
228494567273
106931693908
191690034392
134938724588
106931693896
106931693226
140788123843
155385451308
111856217326
110170204124
228494567397
228494568703
125643111389
228494567464
2...

result:

ok 30 lines

Test #6:

score: 0
Accepted
time: 210ms
memory: 5028kb

input:

3000
684920
881740
317776
310160
23336
999832
819596
973868
166
449876
290325
912538
999939
282224
600310
448121
816943
972518
895590
612220
349205
52931
999880
267637
549817
513310
182
852220
314635
377356
96591
628319
999757
597508
896048
116
71393
735158
203
282
68
33305
762621
745035
922434
5853...

output:

67611341
90223986
28005207
27233331
1319648
104127915
83003612
101051578
2569
41769873
25235715
93827427
104140754
24424464
58142642
41582414
82697155
100892535
91843138
59465231
31217321
3478468
104133259
22974376
52576328
48594603
2923
86785163
27686009
34130245
7039269
61257408
104119319
57832117...

result:

ok 3000 lines