UVa 10820

From Algorithmist
Jump to navigation Jump to search

10820 - Send a Table[edit]

Summary[edit]

Given a number , find the cumulative sum of the number of numbers relatively prime to .

Explanation[edit]

Use Euler's Phi function, and cache the answers.

Input[edit]

100
1
2
3
4
5
10
20
30
200
300
1000
2000
3000
50000
0

Output[edit]

6087
1
3
7
11
19
63
255
555
24463
54795
608383
2433175
5472375
1519848527