SMPLSUM - Editorial

editorial
, , ,
9

I used different approach.
It’s obvious that for prime number n value of this function is
n * (n - 1) + 1
we can see that for i = 1 to n - 1 gcd (i, n) is 1 and for i = n it’s 1.
The sum is n * (n - 1) + 1.

This function is multiplicative. for composite number n = p * q where
p and q are prime the sum is sum_for_p * sum_for_q
i. e. (p * (p - 1) + 1) * (q * (q - 1) + 1).

for composite number that is power of p let’s say n = p * p.
sum(n) = 1 + p * (p - 1) + p ^ 3 * (p - 1).

for n = p * p * p (i. e. p ^ 3)
sum(n) = sum(p * p) + p ^ 5 * (p - 1)
and so on.

My Solution

10

in fact I learn some skills from bhishma’s code,he use java,and i use C++. my ac code
Nice question!

1 Like
11

@xellos0

Hey, what is meaning of result 1 “The answer is the sum of d⋅φ(d) for all divisors d of N”.And please can you add some more theory about what approach you are exactly using to solve this problem.

1 Like
12

Nice editorial !!!

1 Like
13

Could someone explain the proof of result 1 !

It would help many!!!

14

why can’t v compute gcd using recursion and then loop over from i=0…n. it gives same result…plz help…

15

There’s a tight time limit, so a constant-efficient algorithm is necessary. However, I needed no optimisations whatsoever this way.

1 Like
16

I didn’t find the time limit very tight, yeah it was a bit tough but the test case 3 was set as such that many users would have got WA in it

17

Now that I remember, there was some overflow; I added a note about it. Is that what you mean?

18

Yes, I updated that a while ago. You don’t have to deal with special cases, just cut out p^{2e} as written above.

19

@va1ts7_100 … remove the dot, it’s not so hard :\

20

@aragar done

21

oops! I observed that, in this solution he freed the memory before returning, so freeing variable memory does not count in the final results?

I always thought they calculate the total memory used on the runtime for entire execution and result displays the maximum memory required.

1 Like
22

Instead of finding primes, you could have found lowest prime factor of each number.

https://discuss.codechef.com/questions/76818/prime-factorization-of-large-numbers

23

I also applied sieve for 10000000 but i think the complexity is n log(log(n)) and it should work as it is less than 10^8

24

@bhishma - How did you create an array of 10^7 elements? I thought of this same thing, but dropped the idea as C++ doesn’t allow creation of int arrays of more than 2*10^6 I think.

25

I coded in java , and as far as I know we could create arrays of size 10^8 without any issues.

26

@s1d_3: Stack limit can kill static arrays. Did you actually try submitting a code with a vector<> of that size?

27

@xellos0
Reply??

28

That equivalently means that the result for a number ‘n’ is equal to the product of the result of two numbers ‘n1’ and ‘n2’ iff gcd(n1, n2)=1 i.e. they are coprime.

If n1 and n2 are further represented as the product of two coprime numbers, you eventually reach at the numbers that are “powers of a single prime”.

Now the only task is “how to calculate the result for numbers, which are powers of a single prime?”

This is fairly simple and can be done by summing the phi(d).d for every divisor d of that number.

Have a look on this solution :

https://www.codechef.com/viewsolution/8767177

1 Like